Problem
一个长度为 \(n\) 的序列 \(a\)，设其排过序之后为 \(b\)，其中位数定义为 \(b_{n/2}\)，其中 \(a,b\) 从 \(0\) 开始标号，除法下取整。
给你一个长度为 \(n\) 的序列 \(s\)。
回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 之间，右端点在 \([c,d]\) 之间的子区间中，最大的中位数。
其中 \(a<b<c<d\)。
位置也从 \(0\) 开始标号。
我会使用一些方式强制你在线。
对于 \(100\%\) 的数据，\(1\leq n \leq 20000\)，\(1\leq Q \leq 25000\)，\(1\leq a_i\leq 10 ^ 9\)。
Solution
如果 \(q=1\)。
我们很开心地二分 \(x\)，将 \(<x\) 的标成 \(-1\)，将 \(\geq x\) 的标成 \(1\)，那么我只需要找是否存在一个区间和 \(\geq 0\) 就行了！
因为 \(b<c\)，我们前缀和，找 \([a-1,b-1]\) 最小的和 \([c,d]\) 最大的相减，如果这都不行那就不行了。
现在 \(q\leq 50000\)，非常生气，考虑静态维护一下前缀和，发现可以按照值分成 \(n\) 个版本，两两之间相差一个值（\(1\to -1\)），对应的是区间加。询问是区间 \(\min/\max\)。
可持久化线段树，但是标记永久化。
（标记永久化就是说线段树上的标记不下传，每个节点上的 \(ans\) 只关心自己子树的标记和答案之和，询问时加上祖先的）
Code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
struct node{
int mn,mx;
node operator+(int k){return node{mn+k,mx+k};}
node operator*(node b){return node{min(mn,b.mn),max(mx,b.mx)};}
};
template<int N> struct segtree{
node ans[N<<5]; int tag[N<<5],ch[N<<5][2],tot;
int newnode(int p=0){int q=++tot;return memcpy(ch[q],ch[p],sizeof ch[0]),ans[q]=ans[p],tag[q]=tag[p],q;}
segtree():tot(0){ch[0][0]=ch[0][1]=0,ans[0]=node{0,0},tag[0]=0;}
void maintain(int p){ans[p]=ans[ch[p][0]]*ans[ch[p][1]]+tag[p];}
int build(int l,int r){
int p=newnode();
if(l==r) return ans[p]={l,l},tag[p]=l,p;
int mid=(l+r)>>1;
ch[p][0]=build(l,mid),ch[p][1]=build(mid+1,r);
maintain(p);
return p;
}
int modify(int k,int L,int R,int p,int l,int r){
int q=newnode(p);
if(L<=l&&r<=R) return ans[q]=ans[q]+k,tag[q]+=k,q;
int mid=(l+r)>>1;
if(L<=mid) ch[q][0]=modify(k,L,R,ch[p][0],l,mid);
if(mid<R) ch[q][1]=modify(k,L,R,ch[p][1],mid+1,r);
maintain(q);
return q;
}
node query(int L,int R,int p,int l,int r){
if(L<=l&&r<=R) return ans[p];
int mid=(l+r)>>1;
if(L<=mid&&mid<R) return query(L,R,ch[p][0],l,mid)*query(L,R,ch[p][1],mid+1,r)+tag[p];
if(L<=mid) return query(L,R,ch[p][0],l,mid)+tag[p];
if(mid<R) return query(L,R,ch[p][1],mid+1,r)+tag[p];
return assert(0),node{};
}
};
template<int N> struct flower{
int b[N+10],cnt;
flower():cnt(0){}
void add(int x){b[++cnt]=x;}
void build(){sort(b+1,b+cnt+1),cnt=unique(b+1,b+cnt+1)-b-1;}
int operator()(int x){return lower_bound(b+1,b+cnt+1,x)-b;}
int operator[](int x){return b[x];}
};
int n,Q,a[1<<16],root[1<<16];
flower<1<<16> b;
segtree<1<<16> t;
vector<int> pos[1<<16];
int binary(int L,int R,int l1,int r1,int l2,int r2){
int ans=0;
bool flag=0;
if(!l1) flag=1,l1=1;
for(int mid=(L+R)>>1;L<=R;mid=(L+R)>>1){
int lmn=t.query(l1,r1,root[mid],1,n).mn;
if(lmn>0&&flag) lmn=0;
int rmx=t.query(l2,r2,root[mid],1,n).mx;
debug("mid=%d,mn[%d,%d,flag=%d]=%d,mx[%d,%d]=%d\n",mid,l1,r1,flag,lmn,l2,r2,rmx);
if(rmx>=lmn) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b.add(a[i]);
b.build();
for(int i=1;i<=n;i++) pos[a[i]=b(a[i])].push_back(i);
root[0]=t.build(1,n);
for(int i=1;i<=n;i++){
root[i]=root[i-1];
for(int x:pos[i-1]) root[i]=t.modify(-2,x,n,root[i],1,n);
for(int j=1;j<=n;j++) debug("%d%c",t.query(j,j,root[i],1,n).mx," \n"[j==n]);
}
scanf("%d",&Q);
for(int i=1,_=0;i<=Q;i++){
vector<int> q(4);
for(int&x:q) scanf("%d",&x),x+=_,x%=n,x++;
sort(q.begin(),q.end());
debug("ask(%d,%d,%d,%d)\n",q[0],q[1],q[2],q[3]);
printf("%d\n",_=b[binary(1,n,q[0]-1,q[1]-1,q[2],q[3])]);
}
return 0;
}