【bzoj2653】【middle】【主席树+二分答案】

时间：2021-07-03 12:10:52

Description

一个长度为 n 的序列 a ，设其排过序之后为 b ，其中位数定义为 b[n/2] ，其中 a,b 从 0 开始标号 , 除法取下整。 
给你一个长度为 n 的序列 s 。回答 Q 个这样的询问 ： s 的左端点在 [a,b] 之间 , 右端点在 [c,d] 之间的子序列中 ，最大的中位数。 
其中 a

Solution

对着题解理解了半天……又对着代码调了半天……最后发现竟然是一个函数名没写orz

不过不得不说这题真的是主席树好题

先考虑二分答案，找出区间内比mid小的数有多少

因为对答案的贡献只有有或没有，所以可以把比mid小的都设为-1，比mid大的都设为1，如果区间内的和大于等于0，说明mid可行，继续二分下去

然而如果离散之后对每一个值建树，空间毫无疑问爆炸

于是只要用主席树维护一下就可以了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char obuf[<<],*o=obuf;

 inline void print(int x){

     if(x>) print(x/);

     *o++=x%+;

 }

 const int N=,M=N*;

 int n,Pre,q,cnt;

 int rt[N],p[];

 struct node{

     int l,r,lmx,rmx,sum;

 }t[M],op;

 struct data{

     int x,id;

     inline bool operator <(const data &b)const

     {return x<b.x;}

 }a[N];

 inline void pushup(int x){

     t[x].sum=t[t[x].l].sum+t[t[x].r].sum;

     t[x].lmx=max(t[t[x].l].lmx,t[t[x].l].sum+t[t[x].r].lmx);

     t[x].rmx=max(t[t[x].r].rmx,t[t[x].r].sum+t[t[x].l].rmx);

 }

 void build(int &now,int l,int r){

     now=++cnt;

     if(l==r){t[now].lmx=t[now].rmx=t[now].sum=;return;}

     int mid=(l+r)>>;

     build(t[now].l,l,mid);

     build(t[now].r,mid+,r);

     pushup(now);

 }

 void update(int last,int &now,int l,int r,int k){

     now=++cnt;

     if(l==r){t[now].lmx=t[now].rmx=t[now].sum=-;return;}

     int mid=(l+r)>>;

     if(k<=mid) t[now].r=t[last].r,update(t[last].l,t[now].l,l,mid,k);

     else t[now].l=t[last].l,update(t[last].r,t[now].r,mid+,r,k);

     pushup(now);

 }

 node merge(node x,node y){

     node z;

     z.sum=x.sum+y.sum;

     z.lmx=max(x.lmx,x.sum+y.lmx);

     z.rmx=max(y.rmx,y.sum+x.rmx);

     return z;

 }

 node find(int x,int l,int r,int y,int z){

     if(y>z) return op;

     if(l==y&&r==z) return t[x];

     int mid=(l+r)>>;

     if(z<=mid) return find(t[x].l,l,mid,y,z);

     else if(y>mid) return find(t[x].r,mid+,r,y,z);

     else return merge(find(t[x].l,l,mid,y,mid),find(t[x].r,mid+,r,mid+,z));

 }

 int query(int x){

     return find(rt[x],,n,p[],p[]).rmx+find(rt[x],,n,p[]+,p[]-).sum+find(rt[x],,n,p[],p[]).lmx;

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read();

     for(int i=;i<=n;++i) a[i].x=read(),a[i].id=i;

     sort(a+,a++n);

     build(rt[],,n);

     for(int i=;i<=n;++i) update(rt[i-],rt[i],,n,a[i-].id);

     q=read();

     while(q--){

         int x=read(),y=read(),z=read(),k=read();

         p[]=(x+Pre)%n+,p[]=(y+Pre)%n+,p[]=(z+Pre)%n+,p[]=(k+Pre)%n+;

         sort(p+,p+);

         int l=,r=n,ans=;

         while(l<=r){

             int mid=(l+r)>>;

             int f=query(mid);

             if(f>=) ans=mid,l=mid+;

             else r=mid-;

         }

         Pre=a[ans].x;

         print(a[ans].x),*o++='\n';

     }

     fwrite(obuf,o-obuf,,stdout);

     return ;

 }

相关文章