[国家集训队2012]middle

阅读量：4544 次

发布时间：2019-06-08

本文共 3320 字，大约阅读时间需要 11 分钟。

二分答案x

把区间内>=x的数设为1，<x的数设为-1

左端点在[a,b]之间,右端点在[c,d]之间的子序列中，若中位数>=x，

那么 [b+1,c-1]的区间和+[a,b]的最大右子段和+[c,d]的最大左子段和>=0

查询可以用线段树

多组询问，不能每一次二分都重设1和-1

所以用主席树

其中第i棵线段树表示<=i的都被设成了-1

因为主席树是线段树的前缀和，所以一次修改只需要改第i棵线段树，就可以得到<=i的都被设成-1的线段树

#include
     
      #include
      
       #include
       
        #define N 20001using namespace std;int n;pair
        
         a[N];int cnt;int root[N],lc[N*20],rc[N*20];int q[4];struct node{    int sum,lmax,rmax;        node operator + (node p)    {        node c;        c.sum=sum+p.sum;        c.lmax=max(lmax,sum+p.lmax);        c.rmax=max(p.rmax,rmax+p.sum);        return c;    }    }e[N*20],zero;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void build(int &k,int l,int r){    k=++cnt;    if(l==r)     {        e[k].sum=e[k].lmax=e[k].rmax=1;         return;     }    int mid=l+r>>1;     build(lc[k],l,mid);    build(rc[k],mid+1,r);    e[k]=e[lc[k]]+e[rc[k]];}void change(int pre,int &k,int l,int r,int pos){    k=++cnt;    if(l==r)    {        e[k].sum=e[k].lmax=e[k].rmax=-1;        return;    }    int mid=l+r>>1;    if(pos<=mid)     {        rc[k]=rc[pre];        change(lc[pre],lc[k],l,mid,pos);    }    else     {        lc[k]=lc[pre];        change(rc[pre],rc[k],mid+1,r,pos);    }    e[k]=e[lc[k]]+e[rc[k]];}node query(int k,int l,int r,int opl,int opr){    if(opl>opr) return zero;    if(l>=opl && r<=opr) return e[k];    int mid=l+r>>1;    if(opr<=mid) return query(lc[k],l,mid,opl,opr);    if(opl>mid) return query(rc[k],mid+1,r,opl,opr);    return query(lc[k],l,mid,opl,opr)+query(rc[k],mid+1,r,opl,opr);}bool check(int pos){    if(query(root[pos],1,n,q[0],q[1]).rmax+query(root[pos],1,n,q[1]+1,q[2]-1).sum+query(root[pos],1,n,q[2],q[3]).lmax>=0) return true;    return false;}int main(){    freopen("nt2012_middle.in","r",stdin);    freopen("nt2012_middle.out","w",stdout);    read(n);    for(int i=1;i<=n;++i)    {        read(a[i].first);        a[i].second=i;    }    sort(a+1,a+n+1);    build(root[0],1,n);    for(int i=1;i<=n;++i) change(root[i-1],root[i],1,n,a[i].second);    int m;    read(m);    int ans=0;    int l,r,mid;    while(m--)    {        for(int i=0;i<4;++i)        {            read(q[i]);            q[i]+=ans;            q[i]%=n;            q[i]++;        }        sort(q,q+4);        l=0,r=n;        while(l<=r)        {            mid=l+r>>1;            if(check(mid-1)) ans=mid,l=mid+1;            else r=mid-1;        }        ans=a[ans].first;        cout<
         
          <<'\n';    }}