在天数 \(k\) 固定时，定义 \(p_i\) 为第 \(i\) 个连续段的起点。那么一个贪心是在保证第 \(i\) 段的 \(\max=a_{p_i}\) 时尽量最小化 \(a_{p_{i+1}}\)。于是有 \(p_{i+1}=\arg\min\limits\left\{a_j\mid p_i+1\le j\le \min(r_{p_i},n-k+i+1)\right\}\)。注意最后一个位置可能要特判。
对于原题，考虑对 \(k\) 从小往大扫，动态维护所有的 \(p\)。每次 \(k\) 增大只会让 \(n-k+i+1\) 减小 \(1\)，如果这使 \(p_{i+1}\) 变化，那么 \(p_{i+1}=n-k+i+1\)，于是之后的 \(j\ge i+1\) 也有 \(p_j=n-k+j\)。
考虑维护出所有的连续段，每次只会删一段，我们只要支持快速加入一段。注意到从 \(p_i\) 推出 \(p_{i+1}\) 时，\(p_{i+1}\) 只和 \(k-i\) 有关，且 \(p_{i+1}=p_i+1\) 需要 \(k-i\) 不小于一个阈值 \(lim_i\)。这个 \(lim\) 是可以预处理的。找一段的右端点二分即可。
总复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
template <typename T> void Chkmax(T &x, T y) { x = max(x, y); } const int kN = 3e5 + 5, kLog = 20;
int n, q, c;
int a[kN], lim[kN];
int ri[kN], suf[kN];
int qk[kN], qi[kN], ans[kN];
vector<int> qry[kN];struct ST1 {int mn[kLog][kN];int Min(int x, int y) { return (a[x] < a[y]) ? x : y; }void Build() {iota(mn[0] + 1, mn[0] + n + 1, 1);for(int i = 1; i < kLog; i++) {for(int l = 1; l + (1 << i) - 1 <= n; l++) {mn[i][l] = Min(mn[i - 1][l], mn[i - 1][l + (1 << i - 1)]);}}}int ArgMin(int l, int r) {int p = __lg(r - l + 1);return Min(mn[p][l], mn[p][r - (1 << p) + 1]);}
}st1;struct ST2 {int mx[kLog][kN];void Build() {memcpy(mx[0], lim, sizeof(mx[0]));for(int i = 1; i < kLog; i++) {for(int l = 0; l + (1 << i) - 1 <= n; l++) {mx[i][l] = max(mx[i - 1][l], mx[i - 1][l + (1 << i - 1)]);}}}int FindR(int x, int v) {for(int i = kLog - 1; ~i; i--) {if(x + (1 << i) - 1 > n) continue;if(mx[i][x] <= v) x += (1 << i);}return x - 1;}
}st2;void Init() {stack<int> stk;for(int i = 0; i <= n + 1; stk.push(i++)) {while(stk.size()) {int top = stk.top();if(a[top] < a[i]) ri[top] = i, stk.pop();else break;}}for(int i = n; i; i--) suf[i] = max(suf[i + 1], a[i]);
}struct Node {int l, r, v;Node() { }Node(int _l, int _r, int _v) {l = _l;r = _r;v = _v;}
};
Node seg[kN]; int main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];a[n + 1] = n + 1;Init();st1.Build();for(int i = 1; i <= n; i++) {int l = i + 1, r = ri[i] + 1;while(l + 1 < r) {int mid = (l + r) >> 1;(st1.ArgMin(i + 1, mid) == i + 1) ? (l = mid) : (r = mid);}if(r <= ri[i]) lim[i] = n + i - r + 2;}st2.Build();for(int i = 1; i <= q; i++) {cin >> qk[i] >> qi[i];qry[qk[i]].push_back(i);if(qk[i] == 1) ans[i] = n;if(qk[i] == n) ans[i] = a[qi[i]];}seg[c = 1] = Node(0, 0, 0);for(int k = 2; k < n; k++) {int t = k - 2;while(c && (seg[c].v > n - k)) t = seg[c--].l - 1;for(int i = t; i < k; i++) { int pi = seg[c].v;if(pi == n - k) {seg[++c] = Node(i + 1, k - 1, pi);break;}if(lim[pi + i] <= pi + k) {int pos = st2.FindR(pi + i, pi + k) - pi;seg[++c] = Node(i + 1, pos + 1, pi);i = pos;continue;}int tp = pi + i;int pn = st1.ArgMin(tp + 1, min(n - k + i + 1, ri[tp])) - i - 1;seg[++c] = Node(i + 1, i + 1, pn);}for(int i : qry[k]) {int t = min(qi[i], k - 1);int l = 0, r = c + 1;while(l + 1 < r) {int mid = (l + r) >> 1;(seg[mid].r < t) ? (l = mid) : (r = mid);}int res = seg[r].v + t;if(qi[i] < k) ans[i] = a[res];else ans[i] = suf[min(ri[res], n)];}}for(int i = 1; i <= q; i++) cout << ans[i] << "\n";return 0;
}
wp)
