【解题报告】[国家集训队]middle

数据结构主席树

解题报告

发布日期: 2020-08-26

阅读次数:

题目链接

前言

~~为什么会爆栈啊，那么爆栈是什么呢，小编也不知道爆栈是什么，如果你有关于爆栈的看法，欢迎留言(留言区已关闭~~，调了一晚上+一早上，虽然过了，仍然有一些小问题，将在后文提出

题目大意

给你一个长度为 $n$ 的序列，同时给你 $m$ 个询问，求一个字串 $S$ ，其左端点在 $[a,b]$ ，右端点在 $[c,d]$ 内，求其最大的中位数

题解

看到有关中位数的题，我们很清晰的知道可以二分中位数的值，并将大于等于它的赋为 $1$ ，小于它的赋为 $-1$

同时，我们容易发现，区间$[b+1,c-1]$是必选的区间，所以我们只需要在 $[a,b]$ 选(至少选一个的)最大后缀，和在 $[c,d]$ 选(至少选一个的)最大前缀即可

感性理解一下，我们要使中位数最大，则应该尽量贪心的选比它大的数，致使其尽量合法

这样做的复杂度是 $O(nm\log n)$ 的。我们考虑建一棵主席树，主席树的建在原区间上，但是按照原序列的数的权值的从小到大开始建，同样的，一开始我们给每个叶子节点赋初值为 $1$ ，让 $rt[i]$ 表示从排序后第 $i$ 个值的树，其中所有在 $i$ 之前的值的位置上的数都为 $-1$ ，在其之后(包括它自己)都为 $1$ ，这样我们就可以 $O(m\log n)$ 的完成上述操作

代码

inline node merge(node &c,node a,node b)
{
    c.sum=a.sum+b.sum;
    c.lsum=max(a.lsum,a.sum+b.lsum);
    c.rsum=max(b.rsum,b.sum+a.rsum);
    return c;
}

void build(int &u,int l,int r)
{
    if(!u)u=++tot;
    if(l==r)return tr[u].sum=tr[u].lsum=tr[u].rsum=1,void();
    int mid=(l+r)>>1;
    build(tr[u].ls,l,mid);
    build(tr[u].rs,mid+1,r);
    merge(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}

void insert(int &u,int pre,int l,int r,int pos,int val)
{
    if(!u)u=++tot;
    tr[u]=tr[pre];
    if(l==r)return tr[u].sum=tr[u].lsum=tr[u].rsum=val,void();
    int mid=(l+r)>>1;
    if(mid>=pos)
        insert(tr[u].ls=0,tr[pre].ls,l,mid,pos,val);
    else
        insert(tr[u].rs=0,tr[pre].rs,mid+1,r,pos,val);
    merge(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}

int query_sum(int u,int l,int r,int x,int y)
{
    if(l>r)return 0;
    if(l>=x&&r<=y)return tr[u].sum;
    int mid=(l+r)>>1;
    int res=0;
    if(mid>=x)res+=query_sum(tr[u].ls,l,mid,x,y);
    if(mid<y)res+=query_sum(tr[u].rs,mid+1,r,x,y);
    return res;
}

node query__sum(int u,int l,int r,int x,int y)
{
    if(l>=x&&r<=y)return tr[u];
    int mid=(l+r)>>1;
    node res;
    if(mid>=x&&mid>=y)return query__sum(tr[u].ls,l,mid,x,y);
    if(mid<y&&mid<x)return query__sum(tr[u].rs,mid+1,r,x,y);
    return merge(res,query__sum(tr[u].ls,l,mid,x,y),query__sum(tr[u].rs,mid+1,r,x,y));
}

int check(int val,int l,int r,int x,int y)
{
    int res=0;
    res+=query_sum(rt[val],1,n,r+1,x-1);
    res+=query__sum(rt[val],1,n,l,r).rsum;
    res+=query__sum(rt[val],1,n,x,y).lsum;
    return res>=0;
}

signed main(void)
{
    n=read();
    for(register int i=1;i<=n;++i)a[i].val=read(),a[i].pos=i;
    sort(a+1,a+1+n,cmp);
    build(rt[1],1,n);
    for(register int i=2;i<=n;++i)
        insert(rt[i],rt[i-1],1,n,a[i-1].pos,-1);
    p=read();
    int lastans=0,q[4];
    for(register int i=1;i<=p;++i)
    {
        q[0]=(read()+lastans)%n,q[1]=(read()+lastans)%n,q[2]=(read()+lastans)%n,q[3]=(read()+lastans)%n;
        sort(q,q+4);
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid,q[0]+1,q[1]+1,q[2]+1,q[3]+1))l=mid+1,lastans=mid;
            else r=mid-1;
        }
        lastans=a[lastans].val;
        printf("%d\n",lastans);
    }
    return 0;
}