[BZOJ2653]middle

题面

一个长度为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]。　　

输入保证满足条件。

第一行所谓“排过序”指的是从小到大排序！

n<=20000,Q<=25000

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

思路

这道题也是蛮有意思的。我们思考一下，对于单次查询该怎么做。

这里有一个针对中位数的数据结构题的小trick：把大于x的设置为1，小于x的设置为-1，等于x的设置为0。很显然，如果\(sum\)大于0则中位数比x更大，小于0则中位数比x更小，等于0则中位数为x。（在这道题中我们可以把\(sum\)为0的情况归类到中位数大于x里面，原因下面会说）

有了上面这个小trick，我们就可以判断任何一个数和中位数的关系。那么很显然这里可以使用二分。那么问题来了，二分的复杂度是\(O(\log n)\)，如果我们对于每一次二分都重新求和，复杂度是\(O(n)\)，对于q次查询，总复杂度为\(O(qn\log n)\)，很显然是要炸的。

我们发现复杂度里的\(O(q \log n)\)是不能省的（强制在线的查询和二分），那我们就要试图做到\(\log n\)判断一个数是否为中位数。

我们发现，在二分寻找中位数时，不是每一次判断都需要修改全树的。在每次缩小查询范围后（l或r变为mid），范围外的数和下一次二分的数的大小关系是始终不变的，所以我们可以继承上一次修改的结果而不需要再次修改。

另外，对于这种多次查询又是强制在线的数据结构题，我们可以把所有潜在答案计算出来，再用可持久化数据结构储存。

那么整理一下思路，解法如下：

1. 先构建一个可持久化线段树，每个叶子节点对应一个序列上的位置，节点初始值为1（毕竟最开始二分的值是无限小）。
2. 按照从小到大的顺序加入元素（值为-1）。每加入一次就相当于现在中位数可能的值增加。
3. 对于每次查询，我们可以用线段树操作\(maxl(a,b)+sum(b,c)+maxr(c,d)\)来求得中位数的“判定值”。
4. 对于每次查询，二分一下答案对应的版本即可。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn (int)(2e4+1000)#define ll long longusing namespace std;int n,q,idx;ll sum[maxn<<5],lmax[maxn<<5],rmax[maxn<<5];int ls[maxn<<5],rs[maxn<<5],rt[maxn],pre,b[7];struct gg{    int num,loc;}a[maxn];void push_up(int x){    sum[x]=sum[ls[x]]+sum[rs[x]];    lmax[x]=max(sum[ls[x]]+lmax[rs[x]],lmax[ls[x]]);    rmax[x]=max(sum[rs[x]]+rmax[ls[x]],rmax[rs[x]]);    return;}int build(int l,int r){    int now=++idx;    if(l==r){        sum[now]=lmax[now]=rmax[now]=1;        return now;    }    int mid=(l+r)>>1;    ls[now]=build(l,mid);    rs[now]=build(mid+1,r);    push_up(now);    return now;}bool cop(gg x,gg y){return x.num
        
         >1;    if(tar<=mid)ls[now]=update(ls[last],l,mid,tar,val);    else{rs[now]=update(rs[last],mid+1,r,tar,val);}    push_up(now);    return now;}ll get_sum(int now,int l,int r,int tl,int tr){    if(tl<=l&&r<=tr)return sum[now];    int mid=(l+r)>>1;    ll ans=0;    if(tl<=mid)ans+=get_sum(ls[now],l,mid,tl,tr);    if(tr>=mid+1)ans+=get_sum(rs[now],mid+1,r,tl,tr);    return ans;}ll get_rmax(int now,int l,int r,int tl,int tr){    if(r
         
          >1; if(tl<=l&&r<=tr)return rmax[now]; if(tr<=mid)return get_rmax(ls[now],l,mid,tl,tr); if(tl>=mid+1)return get_rmax(rs[now],mid+1,r,tl,tr); return max(get_sum(rs[now],mid+1,r,tl,tr)+get_rmax(ls[now],l,mid,tl,tr),get_rmax(rs[now],mid+1,r,tl,tr));}ll get_lmax(int now,int l,int r,int tl,int tr){ if(r
          
           >1; if(tl<=l&&r<=tr)return lmax[now]; if(tr<=mid)return get_lmax(ls[now],l,mid,tl,tr); if(tl>=mid+1)return get_lmax(rs[now],mid+1,r,tl,tr); return max(get_sum(ls[now],l,mid,tl,tr)+get_lmax(rs[now],mid+1,r,tl,tr),get_lmax(ls[now],l,mid,tl,tr));}bool check(int ves){ ves-=1;ves=rt[ves]; ll ans=get_sum(ves,1,n,b[2],b[3])+max(get_rmax(ves,1,n,b[1],b[2]-1),0ll)+max(0ll,get_lmax(ves,1,n,b[3]+1,b[4])); if(ans>=0)return 1; else return 0;}int main(){// freopen("in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i].num),a[i].loc=i; rt[0]=build(1,n); sort(a+1,a+1+n,cop); for(int i=1;i<=n;i++){ rt[i]=update(rt[i-1],1,n,a[i].loc,-2); } scanf("%d",&q); for(int i=1;i<=q;i++){ for(int j=1;j<=4;j++){ scanf("%d",&b[j]); b[j]=(b[j]+pre)%n; b[j]++; } sort(b+1,b+5); int l=0,r=n; while(l
           
            >1; if(check(mid)){l=mid;} else{r=mid-1;} } printf("%d\n",a[l].num);pre=a[l].num; } return 0;}