題目鏈接：洛谷

題目大意：給定一個長度為$n$的序列，每次詢問左端點在$[a,b]$，右端點在$[c,d]$的所有子區(qū)間的中位數(shù)的最大值。（強(qiáng)制在線）

這里的中位數(shù)定義為，對于一個長度為$n$的序列排序之后為$a_0,a_1,\ldots,a_{n-1}$，則$a_{\lfloor\frac{n}{2}\rfloor}$為這個序列的中位數(shù)。

數(shù)據(jù)范圍：$1\leq n\leq 20000$，$1\leq q\leq 25000$，$1\leq a\leq b\leq c\leq d\leq n$

---

這道題才是真正的主席樹！

首先我們考慮離散化，然后二分答案，判斷這些區(qū)間的中位數(shù)是否有可能$\geq mid$，那怎么判斷呢？

我們發(fā)現(xiàn)，如果把這個序列的所有$\geq mid$的數(shù)改為1，$<mid$的數(shù)改為$-1$，則上述條件等價于這個新的數(shù)列之和非負(fù)。（這是一個非常神仙的套路）

所以我們對于所有的數(shù)$a_i$，預(yù)處理出這個1/-1的序列，但是這樣空間會爆炸。

我們發(fā)現(xiàn)這些序列中，$a_{i-1}$和$a_i$的序列之間僅有一位不同。

于是主席樹閃亮登場。

然后判斷一下左端點在$[a,b]$,右端點在$[c,d]$的最大子段和，判斷一下是否$\geq 0$。

1 #include<cstdio> 2 #include<algorithm> 3 #define Rint register int 4 using namespace std; 5 const int N = 20003; 6 int n, Q, q[4], lans, a[N], id[N], root[N], ls[N << 5], rs[N << 5], cnt; 7 struct Node { 8 int sum, lmax, rmax; 9 inline Node(int s = 0, int l = 0, int r = 0): sum(s), lmax(l), rmax(r){} 10 inline Node operator + (const Node &o) const { 11 return Node(sum + o.sum, max(lmax, sum + o.lmax), max(o.rmax, o.sum + rmax)); 12 } 13 } seg[N << 5]; 14 inline void pushup(int x){ 15 seg[x] = seg[ls[x]] + seg[rs[x]]; 16 } 17 inline void build(int &x, int L, int R){ 18 x = ++ cnt; 19 if(L == R){ 20 seg[x] = Node(1, 1, 1); 21 return; 22 } 23 int mid = L + R >> 1; 24 build(ls[x], L, mid); 25 build(rs[x], mid + 1, R); 26 pushup(x); 27 } 28 inline void change(int &nx, int ox, int L, int R, int pos){ 29 nx = ++ cnt; 30 ls[nx] = ls[ox]; rs[nx] = rs[ox]; 31 if(L == R){ 32 seg[nx] = Node(-1, -1, -1); 33 return; 34 } 35 int mid = L + R >> 1; 36 if(pos <= mid) change(ls[nx], ls[ox], L, mid, pos); 37 else change(rs[nx], rs[ox], mid + 1, R, pos); 38 pushup(nx); 39 } 40 inline Node query(int x, int L, int R, int l, int r){ 41 if(!x || l > r) return Node(); 42 if(l <= L && R <= r) return seg[x]; 43 int mid = L + R >> 1; 44 if(r <= mid) return query(ls[x], L, mid, l, r); 45 else if(mid < l) return query(rs[x], mid + 1, R, l, r); 46 else return query(ls[x], L, mid, l, r) + query(rs[x], mid + 1, R, l, r); 47 } 48 inline int solve(int a, int b, int c, int d){ 49 int l = 1, r = n, mid, tmp; 50 while(l <= r){ 51 mid = l + r >> 1; 52 tmp = query(root[mid], 1, n, a, b).rmax + query(root[mid], 1, n, b + 1, c - 1).sum + query(root[mid], 1, n, c, d).lmax; 53 if(tmp >= 0) l = mid + 1; 54 else r = mid - 1; 55 } 56 return id[r]; 57 } 58 int main(){ 59 scanf("%d", &n); 60 for(Rint i = 1;i <= n;i ++){ 61 scanf("%d", a + i); id[i] = i; 62 } 63 sort(id + 1, id + n + 1, [](int x, int y) -> bool {return a[x] < a[y];}); 64 build(root[1], 1, n); 65 for(Rint i = 1;i < n;i ++) 66 change(root[i + 1], root[i], 1, n, id[i]); 67 scanf("%d", &Q); 68 while(Q --){ 69 for(Rint i = 0;i < 4;i ++){ 70 scanf("%d", q + i); 71 q[i] = (q[i] + lans) % n + 1; 72 } 73 sort(q, q + 4); 74 printf("%d\n", lans = a[solve(q[0], q[1], q[2], q[3])]); 75 } 76 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/AThousandMoons/p/10630747.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的luogu2839 [国家集训队]middle的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。