bzoj2653: middle

Description

　　一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。

　　给你一个长度为n的序列s。

　　回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。

　　其中a<b<c<d。

　　位置也从0开始标号。

　　我会使用一些方式强制你在线。

Input

　　第一行序列长度n。

　　接下来n行按顺序给出a中的数。

　　接下来一行Q。

　　然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。

　　令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。

　　将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。

　　输入保证满足条件。

Output

　　Q行依次给出询问的答案。

Sample Input

5

170337785

271451044

22430280

969056313

206452321

3

3 1 0 2

2 3 1 4

3 1 4 0

Sample Output

271451044

271451044

969056313

HINT

　　0:n,Q<=100

　　1,...,5:n<=2000

　　0,...,19:n<=20000,Q<=25000

 

附大佬博客的详细讲解：

 

个人题解：

 

#include
      
       #include
       
        //#define mid (l+r>>1)#define N 200001using namespace std;int n,m,tot;int root[N],lc[N*20],rc[N*20],cnt;int p[4],ans;pair
        
         a[N];struct node{    int summ,lmax,rmax;}e[N];inline node operator + (node  a,node b){    return (node){a.summ+b.summ,max(a.lmax,a.summ+b.lmax),max(b.rmax,b.summ+a.rmax)};}inline void build(int l,int r,int & k){    k=++cnt;    if(l==r) {e[k].summ=e[k].lmax=e[k].rmax=1;return;}    int mid=l+r>>1;    build(l,mid,lc[k]);build(mid+1,r,rc[k]);    e[k]=e[lc[k]]+e[rc[k]];}inline void insert(int pre,int & now,int l,int r,int k){    now=++cnt;    if(l==r)     {            e[now].summ=e[now].lmax=e[now].rmax=-1;        return;    }    int mid=l+r>>1;    if(k<=mid)     {        rc[now]=rc[pre];        insert(lc[pre],lc[now],l,mid,k);    }     else    {        lc[now]=lc[pre];        insert(rc[pre],rc[now],mid+1,r,k);    }    e[now]=e[lc[now]]+e[rc[now]];}inline node ask(int l,int r,int opl,int opr,int k) {    if(opl>opr) return (node){
    0,0,0};    if(opl==l&&opr==r) return e[k];    int mid=l+r>>1;    if(opr<=mid) return ask(l,mid,opl,opr,lc[k]);    else if(opl>mid) return ask(mid+1,r,opl,opr,rc[k]);    else return ask(l,mid,opl,mid,lc[k])+ask(mid+1,r,mid+1,opr,rc[k]);}bool check(int k){    if(ask(1,n,p[0],p[1],root[k]).rmax+ask(1,n,p[1]+1,p[2]-1,root[k]).summ+ask(1,n,p[2],p[3],root[k]).lmax>=0) return true;     return false;}inline int init(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9') {
    if(c=='-') f=-1;c=getchar();}    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    n=init();    for(int i=1;i<=n;i++) a[a[i].second=i].first=init();    sort(a+1,a+n+1);    build(1,n,root[0]);    for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,n,a[i].second);     m=init();    for(int i=1;i<=m;i++)    {        p[0]=(init()+ans)%n+1;p[1]=(init()+ans)%n+1;p[2]=(init()+ans)%n+1;p[3]=(init()+ans)%n+1;        sort(p,p+4);           int l=1,r=n,mid;           ans=r;           while(l<=r) {mid=l+r>>1; if(check(mid-1)) l=mid+1;else r=mid-1,ans=r;}           ans=a[ans].first;        printf("%d\n",ans);         /*while(l<=r)if(check(mid-1))l=mid+1;else r=mid-1;        printf("%d\n",ans=a[r].first);*/            }}