P4690 镜中的昆虫 (动态区间颜色数) 题解

Statement

• 区间涂颜色
• 区间颜色数

Solution

\(O(\text{polysqrt})\)

略。

\(O(\text{polylog})\)

颜色段均摊有两层含义：

• 随机数据下：任意时刻的颜色段个数期望 \(O(\log n)\)
• 非随机数据下：每次推平时访问的颜色段个数均摊 \(O(n)\)

首先维护每个点 \(i\) 的 \(pre_i\)，一次询问相当于二维偏序。

考虑单点修咋做，他对 \(pre\) 的修改是 \(O(1)\) 的，一次修改看成一次删除 + 一次插入，可以三维偏序完成。

考虑这题咋做。

结论：进行所有区间修改后，\(pre\) 数组的单点修改次数是 \(O(n+m)\) 的。

我们称一个颜色段为一个节点，注意到如果一个节点整体赋上一个值，那么只有节点第一个数、原先最后一个数的后继、现在最后一个数的后继的 \(pre\) 会被修改。

考虑 ODT 的过程，每次修改，我们先将两端的节点分裂，然后删除中间节点，再换成一个同一个节点。

分裂和更换的过程，就是删除若干个节点，再添加至多三个节点。对 \(pre\) 数组的修改次数和删除的节点数同阶。而每个节点至多删除一次，我们添加的节点个数是 \(O(m)\) 的，初始的节点个数是 \(O(n)\) 的。因此，\(pre\) 数组的单点修改次数是 \(O(n+m)\) 的。

既然这样，我们就只需找到 \(pre\) 数组被修改的位置和时间，然后按单点修改的方式做就好了！

怎么找呢？其实就是上面复杂度分析那个过程。我们直接拿个 ODT 维护，然后每次修改就可以找出若干个可能被修改的节点，然后对这些节点求修改后的 \(pre\) 即可。怎么求 \(pre\)？我们对每种颜色开个 ODT 即可。

Code

柯朵莉树写法是跟 251Sec 学的。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10, M = 2e6 + 10;
int n, m, a[N], pre[N], buc[N];
map<int, int> mp;
int btot;

struct Operations {
	int pos, val, tim, xishu, id;
} Oper[M], tmp[M];
int optot, qtot, ans[N];

struct ODTNode {
	int l, r, v;
	bool operator< (const ODTNode& o) const {
		return l < o.l;
	}
};
struct ODT {
	typedef set<ODTNode>::iterator iter;
	set<ODTNode> tr, col[N];
	iter Insert(int l, int r, int v) {
		col[v].insert({l, r, v});
		return tr.insert({l, r, v}).first;
	}
	void Delete(int l, int r, int v) {
		col[v].erase({l, r, v});
		tr.erase({l, r, v});
	}
	iter Split(int p) {
		iter it = tr.lower_bound({p, 0, 0});
		if (it != tr.end() && it->l == p) return it;
		--it;
		int l = it->l, r = it->r, v = it->v;
		Delete(l, r, v);
		Insert(l, p - 1, v);
		return Insert(p, r, v);
	}
	int Pre(int p) {
		iter it = --tr.upper_bound({p, 0, 0});
		if (it->l != p) return p - 1;
		else {
			int v = it->v;
			it = col[v].lower_bound({p, 0, 0});
			if (it != col[v].begin()) return (--it)->r;
			else return 0;
		}
	}
	int Suf(int p) {
		iter it = --tr.upper_bound({p, 0, 0});
		if (it->r != p) return p + 1;
		else {
			int l = it->l, v = it->v;
			it = col[v].lower_bound({l + 1, 0, 0});
			if (it != col[v].end()) return it->l;
			else return n + 1;
		}
	}
	void Assign(int l, int r, int v, int t) {
		iter itr = Split(r + 1), itl = Split(l);
		vector<int> vec;
		for (iter it = itl; it != itr; ++it) {
			int pl = it->l, pr = it->r, pv = it->v, x = Suf(pr);
			vec.push_back(pl);
			if (x > r && x != n + 1) vec.push_back(x);
			col[pv].erase(*it);
		}
		tr.erase(itl, itr);
		Insert(l, r, v);
		int x = Suf(r);
		if (x != n + 1) vec.push_back(x);
		for (int p : vec) {
			Oper[++optot] = {p, pre[p], t, -1, 0};
			Oper[++optot] = {p, pre[p] = Pre(p), t, 1, 0};
		}
	}
} odt;

struct BIT {
	int sum[N];
	BIT() {
		memset(sum, 0, sizeof(sum));
	}
	void Upd(int x, int v) {
		for (++x; x < N; x += x & -x) sum[x] += v;
	}
	int Qry(int x) {
		int res = 0;
		for (++x; x; x -= x & -x) res += sum[x];
		return res;
	}
} bit;

void CDQ(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	CDQ(l, mid), CDQ(mid + 1, r);
	int pos = l;
	rep(j, mid + 1, r) {
		if (!Oper[j].id) continue;
		while (pos <= mid && Oper[pos].pos <= Oper[j].pos) {
			if (!Oper[pos].id) bit.Upd(Oper[pos].val, Oper[pos].xishu);
			++pos;
		}
		ans[Oper[j].id] += Oper[j].xishu * bit.Qry(Oper[j].val);
	}
	rep(i, l, pos - 1) if (!Oper[i].id) bit.Upd(Oper[i].val, -Oper[i].xishu);
	int tp = l;
	for (int i = l, j = mid + 1; i <= mid || j <= r; )
		if (i <= mid && (j > r || Oper[i].pos <= Oper[j].pos)) tmp[tp++] = Oper[i++];
		else tmp[tp++] = Oper[j++];
	rep(i, l, r) Oper[i] = tmp[i];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n) {
		cin >> a[i];
		if (!mp.count(a[i])) mp[a[i]] = ++btot;
		a[i] = mp[a[i]];
		pre[i] = buc[a[i]];
		buc[a[i]] = i;
		Oper[++optot] = {i, pre[i], 0, 1, 0};
		odt.Insert(i, i, a[i]);
	}
	rep(i, 1, m) {
		int op, l, r, x;
		cin >> op >> l >> r;
		if (op == 1) {
			cin >> x;
			if (!mp.count(x)) mp[x] = ++btot;
			x = mp[x];
			odt.Assign(l, r, x, i);
		} else {
			Oper[++optot] = {r, l - 1, i, 1, ++qtot};
			Oper[++optot] = {l - 1, l - 1, i, -1, qtot};
		}
	}
	CDQ(1, optot);
	rep(i, 1, qtot) cout << ans[i] << '\n';
	return 0;
}