CSP-S 模拟赛 Day 19
T1
直接搞，注意判断一下两段数都不完整选上的方案数。
T2
有一个结论是，对于所有的询问，一定可以被拆成 \(O(n)\) 个四元组 \((l0,l1,r0,r1)\)，保证对所有 \(l0 \le l \le l1,r0 \le r \le r1\) 这样的询问，\([l,r]\) 的 \(mex\) 都是相同的。
支配段：对于一类长度越长，值单调递增或者递减的区间，如果要求最值，那么越短的区间肯定比较长的区间要优，所以我们要把较长的区间直接删掉，最后就剩下了 \(O(n)\) 个不交区间。我们可以直接求这个不交区间。
注意到 \(mex\) 是满足支配段所需的性质的，长度增加，\(mex\) 单调不降，所以我们就要求支配段。我们发现当区间扩张的时候，\(mex\) 变化到的值我们不好求，但是如果是收缩区间，那么 \(mex\) 要么不变，要么变成 \(a_i\)。所以考虑倒着扫描线，不难发现当 \(r \to r-1\) 时，从 \(lst_r \to r - 1\) 的区间 \(mex\) 可能变化，并且是取 \(\min\) 的，假设我们改变的区间是 \([l,r]\)，并且原来的 \(mex\) 是 \(x\)，修改位置是 \(p\)，所以在右端点 \([i,p]\) 之间，左端点在 \([l,r]\) 区间时，这些区间的 \(mex\) 都是 \(x\)，那么我们要的支配段就是 \([r,i]\)，\(mex\) 是 \(x\)。当然 \([l,r]\) 之间在修改前可能有很多个 \(mex\)，对于每一个段都要记录一次支配段。直接使用颜色段均摊。
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fir first
#define sec second
// #define memset(a, b) memset(a, b, sizeof(a))
#define memset(a, b, n) memset(a, b, sizeof(int) * (n + 5))
#define endl '\n'
using namespace std;const int N = 1e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, q;
int a[N], p[N], lst[N], ans[N];
map<int, int> mp;
struct node{int l, r, v;bool operator < (const node &rhs) const{return l < rhs.l;}
};
set<node> st;auto split(int x){auto pos = st.lower_bound({x, 0, 0});if (pos -> l == x) return pos;auto [l, r, v] = *--pos;st.erase(pos), st.insert({l, x - 1, v});return st.insert({x, r, v}).fir;
}void cover(int l, int r, int v){auto p1 = split(l), p2 = p1;while (p2 != st.end() && p2 -> v > v) p2++;int R;for (auto i = p1; i != p2; i++){ans[r - i->r + 1] = max(ans[r - i->r + 1], i -> v), R = i -> r;}if (p1 != p2) st.erase(p1, p2), st.insert({l, R, v});
}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) lst[i] = p[a[i]], p[a[i]] = i;set<int> st1;for (int i = 0; i <= n; i++) st1.insert(i);memset(p, 0, n);for (int i = 1; i <= n; i++) st1.erase(a[i]), p[a[i]]++;for (int i = 1; i <= n; i++){st.insert({i, i, *st1.begin()});p[a[i]]--;if (p[a[i]] == 0) st1.insert(a[i]);}for (int i = n; i >= 1; i--){cover(lst[i] + 1, i, a[i]);auto p = split(i);ans[1] = max(ans[1], p -> v);st.erase(p);}for (int i = 1; i <= n; i++) ans[i] = max(ans[i - 1], ans[i]);cin >> q;while (q--){int x; cin >> x;cout << ans[x] << endl;}return 0;
}