题意：给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。 强制在线。 思路：首先考虑二分答案，判断可行的方法则是看是否小于他的数可以比大于他的数多。则考虑对于[b+1, c-1]直接求出来，对于[a, b]求最大的小的减大的后缀，[c, d]求最大前缀，可以建线段树维护。对于每一个数建一个线段树，则空间爆了,考虑使用主席树维护 那么对于第i颗主席树，则是小于 i 的都是-1，大于等于 i 的是1，查询的时候二分答案查询在排名 i 的这颗树上查是否能选出序列使得和大于等于0#include#include #include #include #include #define MAXN 20050using namespace std;inline int read(){ int f = 1, ret = 0; char ch = getchar(); while(ch < '0' || ch > '9') if(ch == '-') f = -1, ch = getchar(); while(ch >= '0' && ch <= '9') ret = ret*10+int(ch-'0'), ch = getchar(); return ret*f;}void print(int x){ if(x < 10) putchar(x+'0'); else{ print(x/10); putchar(x%10+'0'); }}int n, cnt, Q, lastans, q[4], root[MAXN];struct node1{ int id, num; bool operator < (const node1 &x) const{ return num < x.num; } node1(){} node1(int _id, int _num){ id = _id, num = _num; }}a[MAXN<<2];struct data{ int lmax, rmax, tot;};struct node{ int ls, rs; data d;}t[MAXN<<6];data merge(data a, data b){ data ret; ret.tot = a.tot + b.tot; ret.lmax = max(a.lmax, a.tot + b.lmax); ret.rmax = max(b.rmax, b.tot + a.rmax); return ret;}void build(int &u, int l, int r){ int tmp = u; u = ++cnt; t[u] = t[tmp]; if(l == r) {t[u].d.tot = t[u].d.lmax = t[u].d.rmax = 1; return;} int mid = (l+r)>>1; build(t[u].ls, l, mid); build(t[u].rs, mid+1, r); t[u].d = merge(t[t[u].ls].d, t[t[u].rs].d);}void update(int &u, int l, int r, int x){ int tmp = u; u = ++cnt; t[u] = t[tmp]; if(l == r){t[u].d.tot = t[u].d.lmax = t[u].d.rmax = -1; return;} int mid = (l+r)>>1; if(x <= mid) update(t[u].ls, l, mid, x); else update(t[u].rs, mid+1, r, x); t[u].d = merge(t[t[u].ls].d, t[t[u].rs].d);}data query(int u, int l, int r, int tl, int tr){ if(tl <= l && r <= tr) return t[u].d; int mid = (l+r)>>1; if(tr <= mid) return query(t[u].ls, l, mid, tl, tr); if(mid < tl) return query(t[u].rs, mid+1, r, tl, tr); else return merge(query(t[u].ls, l, mid, tl, tr), query(t[u].rs, mid+1, r, tl, tr));}bool check(int id, int l1, int r1, int l2, int r2){ int ret = 0; if(r1+1 <= l2-1) ret += query(root[id], 1, n, r1+1, l2-1).tot; ret += query(root[id], 1, n, l1, r1).rmax; ret += query(root[id], 1, n, l2, r2).lmax; //printf("%d %d\n", id, ret); return ret>=0;}/*输入格式：第一行序列长度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*/int main(){ //freopen("1.in", "r", stdin); //freopen("1.out", "w", stdout); scanf("%d", &n); //n = read(); for(int i = 1; i <= n; i++){ scanf("%d", &a[i].num); a[i].id = i; //a[i] = node1(i, read()); } sort(a+1, a+n+1); build(root[1], 1, n); for(int i = 2; i <= n; i++) root[i] = root[i-1], update(root[i], 1, n, a[i-1].id); scanf("%d", &Q);//Q = read(); while(Q--){ for(int i = 0; i < 4; i++) scanf("%d", &q[i]), q[i] = (q[i]+lastans)%n;//q[i] = (read()+lastans)%n; sort(q, q+4); for(int i = 0; i < 4; i++) q[i]++; int l = 1, r = n, mid, ans; while(l <= r){ mid = (l+r)>>1; if(check(mid, q[0], q[1], q[2], q[3])) ans = mid, l = mid+1; else r = mid-1; } printf("%d\n", lastans = a[ans].num); //print(lastans = a[ans].num); putchar('\n'); } return 0;}