[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）。每加入一次就相当于现在中位数可能的值增加。对于每次查询，我们可以用线段树操作\(maxl(a,b)+sum(b,c)+maxr(c,d)\)来求得中位数的“判定值”。对于每次查询，二分一下答案对应的版本即可。

代码

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#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<y.num;}int update(int last,int l,int r,int tar,int val){int now=++idx;lmax[now]=lmax[last]-2,rmax[now]=rmax[last]-2,sum[now]=sum[last]-2;ls[now]=ls[last],rs[now]=rs[last];if(l==r){return now;}int mid=(l+r)>>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<l)return 0;int mid=(l+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<l)return 0;int mid=(l+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];llans=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<r){int mid=(l+r+1)>>1;if(check(mid)){l=mid;}else{r=mid-1;}}printf("%d\n",a[l].num);pre=a[l].num;}return 0;}