[传送门]
题意就是给一排围栏，每个围栏都有一个高度，查询区间$\left[l, r\right]$之间长度为$w$的子区间的最小高度的最大值。
首先，这个最大值肯定是这个区间里的围栏的某个高度，如果是一个未出现过的高度，显然能有更高的高度满足条件。
那么就可以考虑在离散化后的高度数组里二分答案，然后check一下这个区间里是否有连续$w$个围栏的高度大于等于这个答案。
因为答案肯定是出现过的高度这个性质，那么可以考虑以高度建一棵可持久化线段树，先将高度数组离散化排好序，第$i$个版本的线段树代表的是下标位置的围栏的高度是否大于等于$h_i$，然后保存区间前缀最长连续1、后缀最长连续1、区间最长连续1。第$i$个版本由第$i-1$个版本再加上几个单点修改得来。
查询就保存区间最长前缀及最长后缀进行合并，合并过程更新一下答案。
说起来容易想起来难。我菜爆了。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int n, a[N], h[N], root[N], tol, ans; vector<int> G[N]; struct Seg { struct Tree { int lp, rp, len, pre, suf, mx; } tree[N * 25]; inline void pushup(int p) { tree[p].pre = tree[tree[p].lp].pre + (tree[tree[p].lp].pre == tree[tree[p].lp].len ? tree[tree[p].rp].pre : 0); tree[p].suf = tree[tree[p].rp].suf + (tree[tree[p].rp].suf == tree[tree[p].rp].len ? tree[tree[p].lp].suf : 0); tree[p].mx = max(tree[tree[p].lp].suf + tree[tree[p].rp].pre, max(tree[tree[p].lp].mx, tree[tree[p].rp].mx)); } void build(int &p, int l, int r) { p = ++tol; tree[p].len = tree[p].pre = tree[p].suf = tree[p].mx = r - l + 1; if (l == r) return; int mid = l + r >> 1; build(tree[p].lp, l, mid); build(tree[p].rp, mid + 1, r); } void update(int &p, int q, int l, int r, int pos) { tree[p = ++tol] = tree[q]; if (l == r) { tree[p].pre = tree[p].suf = tree[p].mx = 0; return; } int mid = l + r >> 1; if (pos <= mid) update(tree[p].lp, tree[q].lp, l, mid, pos); else update(tree[p].rp, tree[q].rp, mid + 1, r, pos); pushup(p); } pair<int, int> query(int p, int l, int r, int x, int y) { if (x <= l && y >= r) { ans = max(ans, tree[p].mx); return pair<int, int>(tree[p].pre, tree[p].suf); } int mid = l + r >> 1; pair<int, int> L(0, 0), R(0, 0); if (x <= mid) L = query(tree[p].lp, l, mid, x, y); if (y > mid) R = query(tree[p].rp, mid + 1, r, x, y); ans = max(ans, L.second + R.first); return pair<int, int>(L.first + (L.first == tree[tree[p].lp].len ? R.first : 0), R.second + (R.second == tree[tree[p].rp].len ? L.second : 0)); } } seg; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), h[i] = a[i]; sort(h + 1, h + 1 + n); int cnt = unique(h + 1, h + 1 + n) - h - 1; for (int i = 1; i <= n; i++) { int pos = lower_bound(h + 1, h + 1 + cnt, a[i]) - h; G[pos].push_back(i); } seg.build(root[1], 1, n); for (int i = 2; i <= cnt; i++) { root[i] = root[i - 1]; for (int x: G[i - 1]) { seg.update(root[i], root[i], 1, n, x); } } int q; scanf("%d", &q); while (q--) { int x, y, w; scanf("%d%d%d", &x, &y, &w); int res = 0; int l = 1, r = cnt; while (l <= r) { int mid = (l + r + 1) >> 1; ans = 0; seg.query(root[mid], 1, n, x, y); if (ans >= w) l = mid + 1, res = mid; else r = mid - 1; } printf("%d\n", h[res]); } return 0; }
Codeforces 484 E. Sign on Fence
原文：https://www.cnblogs.com/Mrzdtz220/p/11673034.html
