考虑二分最小值，设当前二分出的值为 \(x\)。
那么把区间中 \(\ge x\) 的变成 \(1\)，其余变为 \(0\)，那么就是查询区间内最长全 \(1\) 区间长度是否 \(\ge k\)。
这个类似于区间最大子段和，可以用线段树轻松维护。
而发现每个 \(x\) 都可能被用到，于是换成主席树即可。
时间复杂度 \(\mathcal O(n\log^2n)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = N * 20;
int n, m;
int a[N], b[N], rnk[N];
struct node {
int len, lmx, rmx, mx;
node () = default;
node (int _len, int _lmx, int _rmx, int _mx) {
len = _len, lmx = _lmx, rmx = _rmx, mx = _mx;
}
friend node operator + (const node &lhs, const node &rhs) {
node res;
res.len = lhs.len + rhs.len;
res.lmx = (lhs.lmx == lhs.len) ? lhs.len + rhs.lmx : lhs.lmx;
res.rmx = (rhs.rmx == rhs.len) ? rhs.len + lhs.rmx : rhs.rmx;
res.mx = max(max(lhs.mx, rhs.mx), lhs.rmx + rhs.lmx);
return res;
}
} t[M];
int rt[N], tot, lc[M], rc[M];
void build(int &p, int l, int r) {
p = ++tot;
if (l == r) return t[p] = node(1, 0, 0, 0), void();
int mid = l + r >> 1;
build(lc[p], l, mid), build(rc[p], mid + 1, r);
t[p] = t[lc[p]] + t[rc[p]];
}
void insert(int &p, int q, int l, int r, int x) {
p = ++tot;
lc[p] = lc[q], rc[p] = rc[q];
if (l == r) return t[p] = node(1, 1, 1, 1), void();
int mid = l + r >> 1;
if (x <= mid) insert(lc[p], lc[q], l, mid, x);
else insert(rc[p], rc[q], mid + 1, r, x);
t[p] = t[lc[p]] + t[rc[p]];
}
node query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p];
int mid = l + r >> 1; node res = node(0, 0, 0, 0);
if (x <= mid) res = res + query(lc[p], l, mid, x, y);
if (y > mid) res = res + query(rc[p], mid + 1, r, x, y);
return res;
}
bool check(int x, int l, int r, int k) {
if (query(rt[x], 1, n, l, r).mx >= k) return true;
return false;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i], rnk[i] = i;
sort(b + 1, b + n + 1, [&](int x, int y) {
return x > y;
});
sort(rnk + 1, rnk + n + 1, [&](int x, int y) {
return a[x] > a[y];
});
build(rt[0], 1, n);
for (int i = 1; i <= n; ++i) insert(rt[i], rt[i - 1], 1, n, rnk[i]);
scanf("%d", &m);
while (m--) {
int l, r, k; scanf("%d%d%d", &l, &r, &k);
int L = 1, R = n;
while (L < R) {
int mid = L + R >> 1;
if (check(mid, l, r, k)) R = mid;
else L = mid + 1;
}
printf("%d\n", b[L]);
}
return 0;
}