一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2653
Q行依次给出询问的答案。
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int M = 200005; struct Node{ Node *ls, *rs; int sum, zd[2]; void up(){ sum = ls->sum + rs->sum; zd[0] = max(ls->sum + rs->zd[0], ls->zd[0]); zd[1] = max(rs->sum + ls->zd[1], rs->zd[1]); } }pool[M * 32], *tail = pool, *zero, *root[M]; int a[M]; struct Point{int pos, val;}b[M]; bool cmp(Point a, Point b){ return a.val < b.val; } int n; #define Ls nd->ls, lf, mid #define Rs nd->rs, mid + 1, rg int query(int L, int R, int opt, Node * nd, int lf = 1, int rg = n){ if(L > R)return 0; if(lf >= L && rg <= R){ if(opt == 2)return nd->sum; return nd->zd[opt]; } int mid = (lf + rg) >> 1; int sum = 0; if(opt == 2){ if(L <= mid)sum += query(L, R, opt, Ls); if(R > mid)sum += query(L, R, opt, Rs); return sum; } else if(opt == 0){ if(R > mid)sum = query(L, R, opt, Rs); if(L <= mid)sum = max(query(L, R, 2, Ls) + sum, query(L, R, opt, Ls)); } else { if(L <= mid)sum = query(L, R, opt, Ls); if(R > mid)sum = max(query(L, R, 2, Rs) + sum , query(L, R, opt, Rs)); } return max(sum, 0); } int x; Node * build(int lf = 1, int rg = n){ Node *nd = ++tail; if(lf == rg) nd->sum = nd->zd[0] = nd->zd[1] = 1; else { int mid = (lf + rg) >> 1; nd->ls = build(lf, mid); nd->rs = build(mid + 1, rg); nd->up(); } return nd; } Node * insert(int pos, Node *nd, int lf = 1, int rg = n){ Node *nnd = ++tail; if(lf == rg)nnd->sum = nnd->zd[0] = nnd->zd[1] = -1; else { int mid = (lf + rg) >> 1; if(pos <= mid){ nnd->rs = nd->rs; nnd->ls = insert(pos, Ls); } else { nnd->ls = nd->ls; nnd->rs = insert(pos, Rs); } nnd->up(); } return nnd; } int q[5]; int Query(){ int ans = 0; for(int i = 0; i < 4; i++)q[i]++;//, printf("%d ", q[i]);puts(""); int lf = 1, rg = n; while(lf <= rg){ int mid = (lf + rg) >> 1; int t1 = query(q[1], q[2], 2, root[mid]); int t2 = query(q[0], q[1] - 1, 1, root[mid]); int t3 = query(q[2] + 1, q[3], 0, root[mid]); int tt = t1 + t2 + t3; //printf("%d %d %d %d %d\n", mid, t1, t2, t3, tt); if(tt >= 0)ans = mid, lf = mid + 1; else rg = mid - 1; } //printf("DONE\n"); return b[ans].val; } int main(){ // freopen("1.in","r",stdin); // freopen("my.out","w",stdout); int m; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); b[i].pos = i, b[i].val = a[i]; } sort(b + 1, b + 1 + n, cmp); root[1] = build(); //cout<<root[1]->sum<<endl; for(int i = 2; i <= n; i++){ //b[i].id = i; root[i] = insert(b[i - 1].pos, root[i - 1]); //cout<<root[i]->sum<<endl; } scanf("%d", &m); while(m--){ int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); q[0] = (a+x)%n, q[1] = (b+x)%n, q[2] = (c+x)%n, q[3] = (d+x)%n; sort(q, q + 4); x = Query(); printf("%d\n", x); } }
原文：https://www.cnblogs.com/EdSheeran/p/9502130.html
