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

· · 题解

好牛逼的1道题,思路真心不好想

先二分答案mid,看到中位数这个东西可以比较容易想到把区间中大于等于mid的取1,小于mid的取-1,如果区间之和大于等于0(看题,虽然是向下取整但是序号从0开始,其实就是从1开始,向上取整,所以等于0也可以),那么这个区间的中位数就大于等于mid.这个东西我们可以用线段树维护,同时也很好维护区间最大前缀和以及区间最大后缀和,统计方式为:

设suf[x]为当前区间的最大前缀,Ls为左区间,Rs为右区间,处理完左右儿子之后:

suf[x]=max(suf[Ls],sum[Ls]+suf[Rs])

这样我们就能保证suf是连着区间开头且是最大的

区间最大后缀pre[x]同理:

pre[x]=max(pre[Rs],sum[Rs]+pre[Ls])

有什么用呢?对于每次询问a,b,c,d,[b,c]的区间是肯定包含在内的,所以我们要在线段树中查询区间[b,c]的和 以及[a,b-1]的最大后缀和,[c+1,d]的最大前缀和,这样就能组成1个连续的区间,若该区间大于等于0,那么mid就合法了.

有没有可能二分出的答案不在区间中呢?不可能,因为假设我们当前的mid符合条件但是区间中没有,那么把mid增大为区间中出现过的1个更大的数,必定也符合条件,所以最后的答案肯定在区间中出现过.

但是这只是第一步.接下来要解决怎么把区间中的数变成0和1,如果每二分一次都进行该操作,那么复杂度就是单次O(n),每次查询的复杂度就是O(n\log_2n),还不如直接sort呢

于是我们继续思考,一个数a_i的贡献由-1变成1是在什么时候呢?只有当mid从比a_i大变成比a_i小的时候,那么我们每次把mid增大,只会对a_i=mid的位置造成影响,mid从最小的a_i增大到比最大的a_i还大时,每个数的贡献都只会改变1次,其它部分都可以共用.

看到共用,我们就可以想到主席树了,于是我们把所有可能的mid的情况一起先建1棵主席树,那么每个mid计算区间和的复杂度就只需要log_2n了,所以总时间复杂度O(n\log_2^2n),空间复杂度O(n\log_2n)

代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define MN 20005
#define Ls Tree[x].ls
#define Rs Tree[x].rs
#define getchar() (p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
    int a=0;char c=getchar();
    while(c>57 or c<48)c=getchar();
    while(47<c and c<58){
        a=a*10+c-48;
        c=getchar();
    }
    return a;
}//快读
struct tree{
    int sum,pre,suf,ls,rs;
}Tree[MN<<6|1];
//主席树
int v[MN],q[4],n,m,cnt,N,root[MN],a[MN];
//v用于离散化,a用于输入
vector<int>num[MN];//记录每种数出现的位置
int low_bnd(int x){
    int l=1,r=N+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(v[mid]>x)r=mid;
            else l=mid;
    }
    return l;
}//手动二分
void change(int &x,int l,int r,int loc,int v){
    Tree[++cnt]=Tree[x];x=cnt;
    if(l==r&&loc==l){Tree[x].sum=v;if(v>0)Tree[x].pre=Tree[x].suf=v;return;}
    if(l>loc||r<loc)return;
    int mid=(l+r)>>1;
    change(Ls,l,mid,loc,v);change(Rs,mid+1,r,loc,v);
    Tree[x].sum=Tree[Ls].sum+Tree[Rs].sum;
    Tree[x].suf=max(Tree[Ls].suf,Tree[Ls].sum+Tree[Rs].suf);
    Tree[x].pre=max(Tree[Rs].pre,Tree[Rs].sum+Tree[Ls].pre);
}//维护区间和,区间最大前缀和,区间最大啊后缀和
int asksum(int x,int l,int r,int b,int e){
    if(b<=l&r<=e)return Tree[x].sum;
    if(b>r||e<l)return 0;
    int mid=(l+r)>>1;
    return asksum(Ls,l,mid,b,e)+asksum(Rs,mid+1,r,b,e);
}//求区间和
int asksuf(int x,int l,int r,int b,int e){
    if(b<=l&&r<=e) return Tree[x].suf;
    if(b>r||e<l)return 0;
    int mid=(l+r)>>1;
    return max(asksum(Ls,l,mid,b,e)+asksuf(Rs,mid+1,r,b,e),asksuf(Ls,l,mid,b,e));
}//求最大前缀
int askpre(int x,int l,int r,int b,int e){
    if(b<=l&&r<=e)return Tree[x].pre;
    if(b>r||e<l)return 0;
    int mid=(l+r)>>1;
    return max(askpre(Ls,l,mid,b,e)+asksum(Rs,mid+1,r,b,e),askpre(Rs,mid+1,r,b,e));
}//求最大后缀
int main(){
    n=read();
    for(int i=1;i<=n;++i){v[i]=a[i]=read();}
    m=read();
    sort(v+1,v+1+n);
    N=unique(v+1,v+1+n)-1-v;
    for(int i=1;i<=n;++i){
        a[i]=low_bnd(a[i]);
        num[a[i]].push_back(i);
    }//离散化,记录各个数字的位置
    for(int i=1;i<=n;++i)change(root[N+1],1,n,i,-1);
    for(int i=N;i;--i){
        root[i]=root[i+1];
        for(int j=0;j<num[i].size();++j){
            change(root[i],1,n,num[i][j],1);
        }
    }
    //建树,不一定是单次O(logn),但是肯定是均摊O(nlogn)的
    int ans=0,a,b,c,d;
    for(int i=1;i<=m;++i){
        a=read();b=read();c=read();d=read();
        q[0]=(a+ans)%n;q[1]=(b+ans)%n;q[2]=(c+ans)%n;q[3]=(d+ans)%n;
        sort(q,q+4);
        a=q[0]+1;b=q[1]+1;c=q[2]+1;d=q[3]+1;
        //
        int l=1,r=N+1;
        while(l+1<r){
            int mid=(l+r)>>1;
            int midans=asksum(root[mid],1,n,b,c);
            int lans=askpre(root[mid],1,n,a,b-1);
            int rans=asksuf(root[mid],1,n,c+1,d);
            if(midans+lans+rans>=0) l=mid;
                else r=mid;
        }
        //二分
        ans=v[l];
        printf("%d\n",v[l]);
    }
    return 0;
}