P2839 [國家集訓隊]middle

有一個長度為$n$的序列，有$m$次詢問，每次詢問$a,b,c,d$，為$l\in [a,b],r\in [c,d]$，$[l,r]$區間的中位數最大是多少，強制在線，$1\le n\le 20000,1\le m\le 25000$。

由于有$a\le b\le c\le d$，分三個區間討論$[a,b],[b+1,c?1],[c,d]$，其中$[b+1,c?1]$這個區間是必選的，$[a,b],[c,d]$這倆個區間可選可不選，

我們考慮二分答案，對于$mid\le a_i$的我們設置為$1$，否則我們設置為$?1$，對于選定的區間，如果中位數是等于$mid$的，則一定有區間和$>=0$，

由于我們要使區間中位數盡可能地大，所以我們定然是在$[a,b]$上選一個點$p$在$1,?1$序列上使得$[p,b]$的和最大，在$[c,d]$上選定一個點$q$也是如此。

如此做的話，單次詢問復雜度將會是$O(n\log n\log n)$的，有沒有辦法高效來完成呢，整體二分似乎是一個比較好的方法，但是這題要求在線求解，，，

整理一下上面我們所需要的值，$[b+1,c?1]$的區間和，$[a,b]$區間的后綴最大值，$[c,d]$區間的前綴最大值，

對于任意一個區間的后綴最大值，前綴最大值都可用線段樹維護，同樣的區間和也可以用線段樹維護，

目前我們所需的就是對于任何一個$mid$，我們要精確地知道對于某段區間地前綴最大，前綴最小，區間和，

這里就可以考慮用主席樹，對每個二分地$mid$都建立一顆主席樹，對于每次二分地$mid$是否合法，我們只要到對應地主席樹上查找即可。

#include <bits/stdc++.h>using namespace std;const int N = 2e4 + 10;struct Seg {int l, r, sum; }t[N << 6];int root[N], ls[N << 6], rs[N << 6], num;int a[N], b[N], n, m;Seg operator + (Seg a, Seg b) {Seg ans;ans.sum = a.sum + b.sum;ans.l = max(a.l, a.sum + b.l);ans.r = max(b.r, b.sum + a.r);return ans; }void push_up(int rt) {t[rt] = t[ls[rt]] + t[rs[rt]]; }void build(int &rt, int l, int r) {rt = ++num;if (l == r) {t[rt] = {-1, -1, -1};return ;}int mid = l + r >> 1;build(ls[rt], l, mid);build(rs[rt], mid + 1, r);push_up(rt); }void update(int &rt, int pre, int l, int r, int x) {rt = ++num, ls[rt] = ls[pre], rs[rt] = rs[pre];if (l == r) {t[rt] = {1, 1, 1};return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], ls[pre], l, mid, x);}else {update(rs[rt], rs[pre], mid + 1, r, x);}push_up(rt); }Seg query(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return t[rt];}int mid = l + r >> 1;if (L <= mid && R > mid) {return query(ls[rt], l, mid, L, R) + query(rs[rt], mid + 1, r, L, R);}else if (L <= mid) {return query(ls[rt], l, mid, L, R);}else {return query(rs[rt], mid + 1, r, L, R);} }int aa, bb, cc, dd;bool judge(int x) {int res = 0;res += query(root[x], 1, n, aa, bb).r;if (bb + 1 <= cc - 1) {res += query(root[x], 1, n, bb + 1, cc - 1).sum;}res += query(root[x], 1, n, cc, dd).l;return res >= 0; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);b[i] = i;}scanf("%d", &m);build(root[n + 1], 1, n);sort(b + 1, b + 1 + n, [&] (int x, int y) {return a[x] < a[y];});for (int i = n; i >= 1; i--) {update(root[i], root[i + 1], 1, n, b[i]);}int ans = 0;for (int i = 1; i <= m; i++) {scanf("%d %d %d %d", &aa, &bb, &cc, &dd);aa = (aa + ans) % n + 1, bb = (bb + ans) % n + 1;cc = (cc + ans) % n + 1, dd = (dd + ans) % n + 1;int tmp[5] = {0, aa, bb, cc, dd};sort(tmp + 1, tmp + 4 + 1);aa = tmp[1], bb = tmp[2], cc = tmp[3], dd = tmp[4];int l = 1, r = n;while (l < r) {int mid = l + r + 1 >> 1;if (judge(mid)) {l = mid;}else {r = mid - 1;}}ans = a[b[l]];printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的P2839 [国家集训队]middle（二分 套 主席树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。