[国家集训队]middle

解法

开\(n\)颗线段树，将第\(i\)颗线段树中大于等于第\(i\)小的数权值赋为1,其他的则为-1，对于每个区间维护一个区间和，最大前缀和，最大后缀和。

然后二分答案，查询二分到的答案对应线段树。

\(设s=[a,b-1]的最大后缀和+[b,c]的区间和+[c+1,d]的最大前缀和\)

若\(s\geq 0\),则答案可能更大，否则答案必须变小，仔细想想为什么。

这样不断二分即可。

考虑到开不下那么多线段树，而若排序后相邻线段树维护的序列只有一个元素不同，所以我们考虑用主席树来维护。

然后其实不需要离散化，离散化也没问题。

完整代码

#include<bits/stdc++.h>

#define rg register

#define il inline

using namespace std;

void ssort(int &a,int &b,int &c,int &d){

    if(a>b)swap(a,b);if(a>c)swap(a,c);if(a>d)swap(a,d);

    if(b>c)swap(b,c);if(b>d)swap(b,d);

    if(c>d)swap(c,d);

}

const int N=3e4;

struct code{

    int x,id;

}a[N];

struct tree{

    int x,l,r,L,R,sum;

}t[N*100],ans,fz;

int cmp(code x,code y){return x.x<y.x;}

int root[N],cnt,aa,bb,cc,dd,n;

il void pushup(tree &no,tree l,tree r){

    no.L=max(l.L,l.sum+r.L);

    no.R=max(r.R,r.sum+l.R);

    no.sum=l.sum+r.sum;

}

int build(int l,int r){

    int no=++cnt;

    if(l==r){

        t[no].x=t[no].sum=t[no].L=t[no].R=1;

        return no;

    }

    int mid=l+r>>1;

    t[no].l=build(l,mid);

    t[no].r=build(mid+1,r);

    pushup(t[no],t[t[no].l],t[t[no].r]);

    return no;

}

int modify(int last,int l,int r,int k){

    int no=++cnt;

    if(l==r){

        t[no].x=t[no].sum=-1;

        return no;

    }

    t[no].l=t[last].l;

    t[no].r=t[last].r;

    int mid=l+r>>1;

    if(k<=mid)t[no].l=modify(t[last].l,l,mid,k);

    else t[no].r=modify(t[last].r,mid+1,r,k);

    pushup(t[no],t[t[no].l],t[t[no].r]);

    return no;

}

void query(int no,int l,int r,int L,int R){

    if(l>=L&&r<=R){

        pushup(ans,ans,t[no]);

        return ;

    }

    if(l>R||r<L||R<L)return ;

    int mid=l+r>>1;

    query(t[no].l,l,mid,L,R);

    query(t[no].r,mid+1,r,L,R);

}

int check(int x){

    int s=0;

    ans=fz;query(root[x],1,n,aa,bb-1);s+=ans.R;

    ans=fz;query(root[x],1,n,bb,cc);s+=ans.sum;

    ans=fz;query(root[x],1,n,cc+1,dd);s+=ans.L;

    return s>=0;

}

int main(){

    cin>>n;

    for(int i=1;i<=n;++i){

        scanf("%d",&a[i].x);

        a[i].id=i;

    }

    sort(a+1,a+n+1,cmp);

    root[0]=build(1,n);

    for(int i=1;i<=n;++i)

        root[i]=modify(root[i-1],1,n,a[i].id);

    int q,x=0;

    cin>>q;

    while(q--){

        scanf("%d%d%d%d",&aa,&bb,&cc,&dd);

        aa=(aa+x)%n+1;bb=(bb+x)%n+1;cc=(cc+x)%n+1;dd=(dd+x)%n+1;

        ssort(aa,bb,cc,dd);

        int l=0,r=n;

        while(l!=r){

            int mid=l+r>>1;

            if(check(mid+1))l=mid+1;

            else r=mid;

        }

        x=a[l+1].x;

        printf("%d\n",x);

    }

}

巴特西

[国家集训队]middle

[国家集训队]middle

解法

完整代码

最新文章

热门文章