[HNOI2009] 梦幻布丁

[HNOI2009] 梦幻布丁

题意

给出一个序列 \(a\)，有 \(q\) 次操作，每次修改把序列中一种数全部改为另一种数。

每次询问，查询序列 \(a\) 的颜色段个数。

思路

颜色段只有同一种颜色才有贡献，我们考虑每种颜色开一棵平衡树维护。

每种颜色维护其在原序列中的下标，下标连续的一段区间就是一个颜色段。

每次改变颜色，相当于把两种颜色合并在一起，使用启发式合并即可。

时间复杂度：\(O(n\log^2n)\)。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
template <typename T> 
void read(T& x) {
	x = 0; T f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -f;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x = x * f;
}
void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
struct treap {
	struct node {
		int ls, rs, val;
		int cnt, l, r;	
		int key, siz;
	} t[N];
	int tot, root[N];
	int top, rub[N]; 
	int new_node(int v) {
		int id;
		if (top) id = rub[top --];
		else id = ++ tot;
		t[id].ls = t[id].rs = 0;
		t[id].val = v, t[id].cnt = 1;
		t[id].l = t[id].r = v;
		t[id].key = rand();
		t[id].siz = 1; 
		return id;
	}
	void push_up(int p) {
		t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + 1;
		if (t[p].ls && t[p].rs) {
			t[p].cnt = t[t[p].ls].cnt + t[t[p].rs].cnt + 1;
			t[p].l = t[t[p].ls].l, t[p].r = t[t[p].rs].r;
			if (t[t[p].ls].r == t[p].val - 1) 
				t[p].cnt --; 
			if (t[p].val + 1 == t[t[p].rs].l)
				t[p].cnt --;
		} else if (t[p].ls) {
			t[p].cnt = t[t[p].ls].cnt + 1;
			t[p].l = t[t[p].ls].l, t[p].r = t[p].val;
			if (t[t[p].ls].r == t[p].val - 1) 
				t[p].cnt --; 
		} else if (t[p].rs) {
			t[p].cnt = t[t[p].rs].cnt + 1;
			t[p].l = t[p].val, t[p].r = t[t[p].rs].r;
			if (t[p].val + 1 == t[t[p].rs].l)
				t[p].cnt --;
		} else {
			t[p].cnt = 1;
			t[p].l = t[p].r = t[p].val;			
		}
	}
	void split(int p, int k, int &x, int &y) {
		if (!p) {x = 0, y = 0; return ;}
		if (t[p].val <= k) {
			x = p;
			split(t[p].rs, k, t[p].rs, y);
		} else {
			y = p;
			split(t[p].ls, k, x, t[p].ls);
		}
		push_up(p);
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (t[x].key > t[y].key) {
			t[x].rs = merge(t[x].rs, y);
			push_up(x);
			return x;	
		} else {
			t[y].ls = merge(x, t[y].ls);
			push_up(y);
			return y;
		}
	}
	void insert(int &id, int val) {
		int x, y;
		split(id, val, x, y);
		id = merge(merge(x, new_node(val)), y);
	}
	int query(int id) {return t[id].cnt;}
	void bmerge(int id, int &id2) {
		if (!id) return ;
		if (t[id].ls) bmerge(t[id].ls, id2);
		if (t[id].rs) bmerge(t[id].rs, id2);
		insert(id2, t[id].val);
		rub[++ top] = id;
	}
} T;
int n, m, ans, a[N];
void modify(int x, int y) {
	if (x == y) return ;
	ans -= T.query(T.root[x]);
	ans -= T.query(T.root[y]);
	int id1, id2; // id1 -> id2 
	if (T.t[x].siz < T.t[y].siz) 
		id1 = x, id2 = y;
	else id1 = y, id2 = x; 
	T.bmerge(T.root[id1], T.root[id2]);
	T.root[y] = T.root[id2];
	T.root[x] = 0;
	ans += T.query(T.root[y]);
}
int main() {
	srand(time(0));
	read(n); read(m);
	for (int i = 1; i <= n; i ++) {
		read(a[i]);
		T.insert(T.root[a[i]], i);
	}
	for (int i = 1; i <= 1e6; i ++) 
		ans += T.query(T.root[i]);
	while (m --) {
		int op, x, y;
		read(op);
		if (op == 1) {
			read(x); read(y);
			modify(x, y);
		} else {
			write(ans); putchar('\n');
		}
	}
	return 0;
}