题目链接：洛谷
题目大意：给定一个长度为$n$的序列，每次询问左端点在$[a,b]$，右端点在$[c,d]$的所有子区间的中位数的最大值。（强制在线）
这里的中位数定义为，对于一个长度为$n$的序列排序之后为$a_0,a_1,\ldots,a_{n-1}$，则$a_{\lfloor\frac{n}{2}\rfloor}$为这个序列的中位数。
数据范围：$1\leq n\leq 20000$，$1\leq q\leq 25000$，$1\leq a\leq b\leq c\leq d\leq n$
这道题才是真正的主席树！
首先我们考虑离散化，然后二分答案，判断这些区间的中位数是否有可能$\geq mid$，那怎么判断呢？
我们发现，如果把这个序列的所有$\geq mid$的数改为1，$<mid$的数改为$-1$，则上述条件等价于这个新的数列之和非负。（这是一个非常神仙的套路）
所以我们对于所有的数$a_i$，预处理出这个1/-1的序列，但是这样空间会爆炸。
我们发现这些序列中，$a_{i-1}$和$a_i$的序列之间仅有一位不同。
于是主席树闪亮登场。
然后判断一下左端点在$[a,b]$,右端点在$[c,d]$的最大子段和，判断一下是否$\geq 0$。
#include<cstdio>
#include<algorithm>
#define Rint register int
using namespace std;
const int N = ;
int n, Q, q[], lans, a[N], id[N], root[N], ls[N << ], rs[N << ], cnt;
struct Node {
int sum, lmax, rmax;
inline Node(int s = , int l = , int r = ): sum(s), lmax(l), rmax(r){}
inline Node operator + (const Node &o) const {
return Node(sum + o.sum, max(lmax, sum + o.lmax), max(o.rmax, o.sum + rmax));
}
} seg[N << ];
inline void pushup(int x){
seg[x] = seg[ls[x]] + seg[rs[x]];
}
inline void build(int &x, int L, int R){
x = ++ cnt;
if(L == R){
seg[x] = Node(, , );
return;
}
int mid = L + R >> ;
build(ls[x], L, mid);
build(rs[x], mid + , R);
pushup(x);
}
inline void change(int &nx, int ox, int L, int R, int pos){
nx = ++ cnt;
ls[nx] = ls[ox]; rs[nx] = rs[ox];
if(L == R){
seg[nx] = Node(-, -, -);
return;
}
int mid = L + R >> ;
if(pos <= mid) change(ls[nx], ls[ox], L, mid, pos);
else change(rs[nx], rs[ox], mid + , R, pos);
pushup(nx);
}
inline Node query(int x, int L, int R, int l, int r){
if(!x || l > r) return Node();
if(l <= L && R <= r) return seg[x];
int mid = L + R >> ;
if(r <= mid) return query(ls[x], L, mid, l, r);
else if(mid < l) return query(rs[x], mid + , R, l, r);
else return query(ls[x], L, mid, l, r) + query(rs[x], mid + , R, l, r);
}
inline int solve(int a, int b, int c, int d){
int l = , r = n, mid, tmp;
while(l <= r){
mid = l + r >> ;
tmp = query(root[mid], , n, a, b).rmax + query(root[mid], , n, b + , c - ).sum + query(root[mid], , n, c, d).lmax;
if(tmp >= ) l = mid + ;
else r = mid - ;
}
return id[r];
}
int main(){
scanf("%d", &n);
for(Rint i = ;i <= n;i ++){
scanf("%d", a + i); id[i] = i;
}
sort(id + , id + n + , [](int x, int y) -> bool {return a[x] < a[y];});
build(root[], , n);
for(Rint i = ;i < n;i ++)
change(root[i + ], root[i], , n, id[i]);
scanf("%d", &Q);
while(Q --){
for(Rint i = ;i < ;i ++){
scanf("%d", q + i);
q[i] = (q[i] + lans) % n + ;
}
sort(q, q + );
printf("%d\n", lans = a[solve(q[], q[], q[], q[])]);
}
}