题意

对于一个序列 $b$，定义其权值为满足以下条件的正整数 $k$ 的数量：

• 存在一种将 $b$ 划分成 $k$ 段的方案，使得每一段中没出现的最小正整数相同。

给定长度为 $n$ 的序列 $a$。$q$ 次询问 $l,r$，求 $a[l,r]$ 的权值。$1\leq n,q\leq 6\times 10^5$，$1\leq a_i\leq 4\times 10^5$。

题解

为什么这么典的题还不会呢？我问我自己。

我们先令 $a_i\leftarrow a_i-1$，那么没出现的最小正整数就转化成了 $\operatorname{mex}$。

有很显然的性质：若 $k$ 是合法的，则 $k-1$ 也一定是合法的。考察两个 $\operatorname{mex}=x$ 的数集的并，不难发现其 $\operatorname{mex}$ 值也为 $x$，所以我们可以合并任意两个相邻的段。

根据这个性质，我们还能得出，每个划分出的子段的 $\operatorname{mex}$ 值都应该等于询问区间的 $\operatorname{mex}$ 值。

那么问题其实就是求最多能划分成多少段，使得每段的 $\operatorname{mex}$ 值相同。

对于一个区间 $[l,r]$，若不存在 $[l',r']\subsetneqq[l,r]$ 使得 $\operatorname{mex}(a[l',r'])=\operatorname{mex}(a[l,r])$，则称 $[l,r]$ 是一个极小 $\operatorname{mex}$ 区间。根据经典结论，极小 $\operatorname{mex}$ 区间最多只有 $2n$ 个。

:::info[证明] 考察一个极小 $\operatorname{mex}$ 区间 $[l,r]$，显然 $a_l\neq a_r$。不妨先考察所有 $a_l>a_r$ 的极小 $\operatorname{mex}$ 区间。

根据定义，我们删去 $a_l,a_r$ 中的任何一个都会导致 $\operatorname{mex}$ 值改变，因此可以得到 $\operatorname{mex}(a[l,r])>a_l>a_r$，$\operatorname{mex}(a[l,r-1])=a_r$。

考察某个右端点 $r'$（注意这里要满足 $a_l>a_{r'}$）：

• $l\leq r'<r$：此时 $[l,r']$ 必定不是极小 $\operatorname{mex}$ 区间，因为 $\operatorname{mex}(a[l,r'])\leq a_r$，所以给左端点加 $1$ 不会影响 $\operatorname{mex}$ 值。
• $r<r'\leq n$：此时 $[l,r']$ 同样不是极小 $\operatorname{mex}$ 区间，因为 $\operatorname{mex}(a[l,r])>a_l>a_{r'}$，说明 $a_{r'}$ 已经在 $a[l,r]$ 中出现过了，给右端点减 $1$ 不会影响 $\operatorname{mex}$ 值。

因此每个左端点 $l$ 至多对应 $1$ 个满足 $a_l>a_r$ 的极小 $\operatorname{mex}$ 区间。

同理，可以证明每个右端点 $r$ 至多对应 $1$ 个满足 $a_l<a_r$ 的极小 $\operatorname{mex}$ 区间。$\Box$ :::

极小 $\operatorname{mex}$ 区间可以用颜色段均摊 $\mathcal{O}(n\log{n})$ 找出。具体来说，对左端点做扫描线，维护每个右端点对应区间的 $\operatorname{mex}$，那么每次删除 $a_l$，相当于把所有满足 $r<nxt_l\land \operatorname{mex}(a[l,r])\geq a_l$ 的 $r$ 推平成 $a_l$。$\operatorname{mex}$ 具有单调性，所以容易颜色段均摊维护。而对于每个在推平中将要删除的右端点区间 $[r_1,r_2]$，我们发现其恰好对应一个极小 $\operatorname{mex}$ 区间 $[l,r_1]$。

在扫描线的同时做单点查询，就可以得到每个询问区间的 $\operatorname{mex}$ 值。

需要注意一个细节：我们所删除的右端点区间应当是一个极长颜色段，但是我们在 split 的时候可能会分裂一个极长颜色段，所以需要特判合并回去。可以结合代码理解。

回到本题。我们把 $\operatorname{mex}$ 值相同的询问区间放到一起处理，这里设 $\operatorname{mex}=x$。不难发现，每种子段的划分方式，都能对应于一个被询问区间完全包含的、若干不交的 $\operatorname{mex}=x$ 的极小 $\operatorname{mex}$ 区间构成的集合。

那么问题转化成在询问区间内选择若干不交的 $\operatorname{mex}=x$ 的极小 $\operatorname{mex}$ 区间，最大化选择的区间数量。由于 $\operatorname{mex}$ 值相同的极小区间不成包含关系，所以可以直接贪心跳，那么自然就可以倍增解决。按左端点排序双指针即可求出每个区间跳到的下一个区间在哪儿。

时间复杂度 $\mathcal{O}((n+q)\log{n})$。

代码

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 6e5 + 5, V = 4e5 + 5, INF = 1e9, LGN = 20 + 5;

int mxv, a[N], nxt[N], pos[V], f[LGN][N << 1];
bool vis[V];
struct Range {
	int l, r;
	bool operator<(const Range &x) const { return l < x.l; }
};
struct Query {
	int id, l, r, mex;
	bool operator<(const Query &x) const { return l < x.l; }
} qr[N];
vector<Range> rg[V];

struct ODT {
	struct Node {
		int l, r;
		mutable int v;
		bool operator<(const Node &x) const { return l < x.l; }
	};
	set<Node> s;
	using It = set<Node>::iterator;
	inline It split(int x) {
		auto it = s.lower_bound({x, 0, 0});
		if (it != s.end() && it->l == x) return it;
		--it;
		int l = it->l, r = it->r, v = it->v;
		s.erase(it);
		return s.insert({l, x - 1, v}), s.insert({x, r, v}).first;
	}
	inline int query(int x) {
		auto it = s.lower_bound({x, 0, 0});
		if (it != s.end() && it->l == x) return it->v;
		return (--it)->v;
	}
} odt;

inline void proc(int x) {
	auto &rgs = rg[x];
	int sz = rgs.size();
	for (int i = 0, j = 0; i < sz; ++i) {
		while (j < sz && rgs[j].l <= rgs[i].r) ++j;
		f[0][i] = j;
	}
	for (int i = 0; i <= 20; ++i) f[i][sz] = sz;
	for (int i = 1; i <= 20; ++i) for (int j = 0; j < sz; ++j) f[i][j] = f[i - 1][f[i - 1][j]];
}

vector<int> solve(int n, vector<int> &v, int q, vector<pii> &queries) {
    int lst = 0, p = 1;
    for (int i = 1; i <= n; ++i) {
    	chk_max(mxv, a[i] = --v[i - 1]);
    	vis[a[i]] = 1;
    	int mex = lst;
    	while (vis[mex]) ++mex;
    	if (i > 1 && lst != mex) odt.s.insert({p, i - 1, lst}), p = i;
    	lst = mex;
    }
    odt.s.insert({p, n, lst});
    fill(pos, pos + mxv + 1, n + 1);
    for (int i = n; i; --i) nxt[i] = pos[a[i]], pos[a[i]] = i;
	for (int i = 0, l, r; i < q; ++i) qr[i + 1] = {i, queries[i].first, queries[i].second};
	sort(qr + 1, qr + q + 1);
    for (int l = 1, i = 1; l <= n; ++l) {
    	while (i <= q && qr[i].l == l) qr[i].mex = odt.query(qr[i].r), ++i;
    	auto it = --odt.split(l + 1);
    	rg[it->v].push_back({l, l}), odt.s.erase(it);
    	auto it2 = odt.split(nxt[l]), it1 = it2;
        int x = a[l];
    	while (it1 != odt.s.begin() && prev(it1)->v >= x) --it1, rg[it1->v].push_back({l, it1->l});
    	if (it1 != it2) {
    		int p = it1->l;
    		odt.s.erase(it1, it2), odt.s.insert({p, nxt[l] - 1, a[l]});
    	}
        if (it2 != odt.s.begin() && (it1 = prev(it2))->v == it2->v) {
            int l = it1->l, r = it2->r, v = it2->v;
            odt.s.erase(it1), odt.s.erase(it2), odt.s.insert({l, r, v});
        }
    }
    sort(qr + 1, qr + q + 1, [](const Query &x, const Query &y) { return x.mex < y.mex; });
    vector<int> ans(q);
    for (int i = 1, j = -1; i <= q; ++i) {
    	if (j < qr[i].mex) proc(j = qr[i].mex);
    	int sz = rg[j].size();
    	int p = lower_bound(rg[j].begin(), rg[j].end(), Range{qr[i].l, 0}) - rg[j].begin();
    	int tot = 1, r = qr[i].r;
    	for (int k = 20; ~k; --k)
    		if (f[k][p] < sz && rg[j][f[k][p]].r <= r) tot += 1 << k, p = f[k][p];
    	ans[qr[i].id] = tot;
    }
    return ans;
}