E. Sign on Fence

給定一個長度為$n$的數組$a$，$1\le a_i\le 10^9$，有$m$次詢問，每次給定$l,r,k$，要我們在$[l,r]$區間內找到一個長度為$k$的區間，使得區間最小值最大，輸出最大值。

考慮二分答案，如果當前二分的區間是$[l,r]$，我們把大于$mid$的點，在數組中都設置為$1$，小于等于$mid$的點，在數組中都設置為$0$，

考慮用線段樹維護一個區間最長連續$1$的長度，對于每組詢問，我們每次查詢區間$[l_i,r_i]$的最長連續$1$長度是否大于等于$k_i$即可，

由于單次查詢的復雜度是$O(n\log n\log n)$，所以可以考慮整體二分，復雜度同樣也是$O(n\log n\log n)$的，

整體二分的時候我們先遞歸去處理$[l,mid]$，這個時候不清空線段樹，當我們處理$[mid+1,r]$的時候，再清空線段樹。

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;struct Seg {int l, r, res, len; }a[N << 2];Seg operator + (Seg a, Seg b) {Seg ans;ans.len = a.len + b.len;ans.l = a.l == a.len ? a.l + b.l : a.l;ans.r = b.r == b.len ? b.r + a.r : b.r;ans.res = max({a.res, b.res, a.r + b.l});return ans; }void push_up(int rt) {a[rt] = a[rt << 1] + a[rt << 1 | 1]; }void build(int rt, int l, int r) {if (l == r) {a[rt] = {0, 0, 0, 1};return ;}int mid = l + r >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt); }void update(int rt, int l, int r, int x, int v) {if (l == r) {a[rt] = {v, v, v, 1};return ;}int mid = l + r >> 1;if (x <= mid) {update(rt << 1, l, mid, x, v);}else {update(rt << 1 | 1, mid + 1, r, x, v);}push_up(rt); }Seg query(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return a[rt];}int mid = l + r >> 1;if (L <= mid && R > mid) {return query(rt << 1, l, mid, L, R) + query(rt << 1 | 1, mid + 1, r, L, R);}else if (L <= mid) {return query(rt << 1, l, mid, L, R);}else {return query(rt << 1 | 1, mid + 1, r, L, R);} }struct Res {int l, r, id, k, op; }q[N << 1], q1[N << 1], q2[N << 1];int b[N], ans[N], n, m, tot;void solve(int l, int r, int L, int R) {if (l > r || L > R) {return ;}if (l == r) {for (int i = L; i <= R; i++) {if (q[i].op) {ans[q[i].id] = b[l];}}return ;}int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;for (int i = L; i <= R; i++) {if (q[i].op) {int cur = query(1, 1, n, q[i].l, q[i].r).res;if (cur >= q[i].k) {q2[++cnt2] = q[i];}else {q1[++cnt1] = q[i];}}else {if (q[i].k > b[mid]) {update(1, 1, n, q[i].id, 1);q2[++cnt2] = q[i];}else {q1[++cnt1] = q[i];}}}for (int i = 1; i <= cnt1; i++) {q[L + i - 1] = q1[i];}for (int i = 1; i <= cnt2; i++) {q[L + cnt1 + i - 1] = q2[i];}solve(l, mid, L, L + cnt1 - 1);for (int i = L; i <= R; i++) {if (!q[i].op && q[i].k > b[mid]) {update(1, 1, n, q[i].id, 0);}}solve(mid + 1, r, L + cnt1, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);int cnt = 0;for (int i = 1; i <= n; i++) {scanf("%d", &b[i]);q[++cnt] = {0, 0, i, b[i], 0};}scanf("%d", &m);for (int i = 1, l, r, k; i <= m; i++) {scanf("%d %d %d", &l, &r, &k);q[++cnt] = {l, r, i, k, 1};}sort(b + 1, b + 1 + n);tot = unique(b + 1, b + 1 + n) - (b + 1);build(1, 1, n);solve(1, tot, 1, cnt);for (int i = 1; i <= m; i++) {printf("%d\n", ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的E. Sign on Fence（整体二分 + 线段树维护区间最大连续 1 的个数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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