Description
罗马尼亚贵族们普遍认为，一个整数数组 \(a[0], a[1], a[2], \ldots, a[m - 1]\) 的美丽值定义为：满足以下条件的正整数 \(k\) 的个数——你可以将该数组划分为 \(k\) 个互不重叠的子数组（即连续元素的序列），使得：
- 每个元素恰好属于一个子数组；
- 所有子数组具有相同的最小缺失元素。
这里，一个整数数组的最小缺失元素是指数组中没有出现的、严格大于 \(0\) 的最小正整数。
给定一个整数数组 \(v[0], v[1], \ldots, v[n - 1]\)，以及 \(q\) 个询问，每个询问的形式为 \((l_i, r_i)\)，其中对所有 \(0 \leq i < q\)，均有 \(1 \leq l_i \leq r_i \leq n\)。
对于每个询问，你需要求出数组 \(v[l_i - 1], v[l_i ], \ldots, v[r_i - 1]\) 的美丽值。
Solution
单次询问等价于问 \([l_i,r_i]\) 可以划分成至多多少个区间，满足每个区间的 \(\text{mex}\) 为 \(\text{mex}[l_i,r_i]\)。
有个经典结论是“极短 mex 区间”只有 \(O(n)\) 个，这里的“极短 mex 区间”指的是所有的区间 \([l,r]\)，满足 \(\text{mex}[l,r]\neq\text{mex}[l,r-1]\) 且 \(\text{mex}[l,r]\neq \text{mex}[l+1,r]\)。
证明考虑构造性证明，我们去找到所有的这样的区间 \([l,r]\)。先预处理出所有 \(\text{mex}[1,i]\) 的值，然后从小到大枚举左端点 \(l\)，用 ODT 维护所有 \(\text{mex}[l,r]\) 的值。
每次删掉 \(a_l\) 时，相当于是对于 \(val_i\leftarrow\max(val_i,a_l)(l+1\leq i\leq nxt_l-1)\)，\(nxt_i\) 为 \(i\) 后面第一个和 \(a_i\) 相等的位置。由于 \(val_i\) 具有单调性，所以在 ODT 上 split 出来后直接暴力枚举区间修改即可。而对于所有修改区间 \([l',r',v](v>a_l)\)，都对应了唯一一个极短区间 \([l,l']\)。
也就是说极短区间数量和 ODT 的复杂度是一样的，都是 \(O(n)\)。
由于所有极短区间不存在包含关系，所以对于 \(\text{mex}\) 相同的直接倍增跳即可。
时间复杂度：\(O((n+q)\log n)\)。
Code
#include <bits/stdc++.h>#ifdef ORZXKR
#include "grader.cpp"
#endifconst int kMaxN = 6e5 + 5;int n, q, b;
int a[kMaxN], l[kMaxN], r[kMaxN], res[kMaxN], mex[kMaxN];
std::vector<int> qq[kMaxN];
std::vector<std::pair<int, int>> seg[kMaxN];
std::vector<std::array<int, 20>> nxt[kMaxN];struct ODT {std::set<std::pair<int, int>> st;void init(int n, int *a) {st.clear();for (int i = 1; i <= n; ++i)if (i == 1 || a[i] != a[i - 1])st.emplace(i, a[i]);}void split(int x) {if (x < 1 || x > n) return;auto [p, v] = *--st.lower_bound({x + 1, 0});if (p != x) st.emplace(x, v);}std::vector<std::pair<int, int>> chkmin(int x, int v) {// 对 [1, x] chkmin vsplit(x + 1);auto it = --st.lower_bound({x + 1, 0});std::vector<std::pair<int, int>> vec;for (;; --it) {if (it->second > v) vec.emplace_back(*it);else break;if (it == st.begin()) break;}if (!vec.size()) return vec;std::reverse(vec.begin(), vec.end());for (auto p : vec) st.erase(p);st.emplace(vec[0].first, v);return vec;}int query(int x) {auto it = --st.lower_bound({x + 1, 0});return it->second;}
} odt;void getseg() {static int cnt[kMaxN] = {0}, now[kMaxN], lst[kMaxN], nxt[kMaxN] = {0};for (int i = 1; i <= n; ++i) ++cnt[a[i]];for (int i = 1; i <= 4e5 + 1; ++i) {lst[i] = n + 1;if (!cnt[i]) {now[n] = i; break;}}for (int i = n; i > 1; --i) {now[i - 1] = now[i];if (!--cnt[a[i]]) now[i - 1] = std::min(now[i - 1], a[i]);}for (int i = n; i; --i) nxt[i] = lst[a[i]], lst[a[i]] = i;// for (int i = 1; i <= n; ++i) std::cerr << now[i] << " \n"[i == n];odt.init(n, now);for (int i = 1; i <= n; ++i) {for (auto id : qq[i]) mex[id] = odt.query(r[id]);std::vector<std::pair<int, int>> vec = odt.chkmin(nxt[i] - 1, a[i]);for (auto [p, v] : vec) seg[v].emplace_back(i, p);}
}void getnxt() {for (int i = 1; i <= n + 1; ++i) {std::sort(seg[i].begin(), seg[i].end());nxt[i].resize(seg[i].size());for (int j = (int)seg[i].size() - 1; ~j; --j) {nxt[i][j][0] = std::lower_bound(seg[i].begin(), seg[i].end(), std::pair<int, int>{seg[i][j].second + 1, 0}) - seg[i].begin();for (int k = 1; k <= std::__lg(n); ++k) {if (nxt[i][j][k - 1] == seg[i].size()) nxt[i][j][k] = seg[i].size();else nxt[i][j][k] = nxt[i][nxt[i][j][k - 1]][k - 1];}}}
}void solve() {for (int i = 1; i <= q; ++i) {if (mex[i] == 1) {res[i] = r[i] - l[i] + 1;continue;}int mex = ::mex[i], p = std::lower_bound(seg[mex].begin(), seg[mex].end(), std::pair<int, int>{l[i], 0}) - seg[mex].begin();int ans = 0;if (p < seg[mex].size()) {for (int j = std::__lg(n); ~j; --j) {assert(p < nxt[mex].size());// std::cerr << seg[mex].size() << ' ' << j << ' ' << p << ' ' << nxt[mex][p][j] << '\n';if (nxt[mex][p][j] != seg[mex].size() && seg[mex][nxt[mex][p][j]].second <= r[i]) {p = nxt[mex][p][j], ans += (1 << j);}}}res[i] = ans + 1;}
}std::vector<int> solve(int n, std::vector<int> &v, int q, std::vector<std::pair<int, int>> &queries) {::n = n, ::q = q;for (int i = 1; i <= n; ++i) a[i] = v[i - 1];for (int i = 1; i <= q; ++i) {std::tie(l[i], r[i]) = queries[i - 1];++l[i], ++r[i];qq[l[i]].emplace_back(i);}getseg(), getnxt(), solve();std::vector<int> ans;for (int i = 1; i <= q; ++i) ans.emplace_back(res[i]);return ans;
}