带修莫队全RE求调

#include <bits/stdc++.h>
using namespace std;

struct interval {
	int l, r, id, dfn;
} q[114514];

struct upd {
	int p, c, before;
} upda[114514];
int answer, cnt[114514], kc, n, m, a[114514], ans[114514];
int qcn, rcn;

bool cmp(interval aa, interval bb) {
	if ((aa.l / kc ) == (bb.l / kc))
		return aa.r < bb.r;
	return aa.l < bb.l;
}

void add(int x) {
	if (!cnt[a[x]])
		answer++;
	cnt[a[x]]++;
}

void del(int x) {
	cnt[a[x]]--;
	if (!cnt[a[x]])
		answer--;
}

int  main() {
	scanf("%d%d", &n, &m);
	kc = pow(n, 0.666);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) {
		char qr;
		int ll, rr;
		cin >> qr >> ll >> rr;
		if (qr == 'Q') {
			++qcn;
			q[qcn] = {ll, rr, qcn, rcn};
		}

		else {
			++rcn;
			upda[rcn].c = ll,	upda[rcn].p = rr;

		}

	}

	sort(q + 1, q + qcn + 1, cmp);

	int L = 1, R = 1;
	cnt[a[1]]++;
	answer = 1;
	int nup = 0;

	for (int i = 1; i <= qcn; i++) {
		while (L < q[i].l)
			del(L++);
		while (L > q[i].l)
			add(--L);
		while (R < q[i].r)
			add(++R);
		while (R > q[i].r)
			del(R--);
		while (nup < q[i].dfn) //更新修改

		{
			++nup;
			int upid = upda[nup].c, updd = upda[nup].p;
			if (L <= upid && upid <= R)
				del(upid);
			upda[nup].before = a[upid];
			a[upid] = updd;
			if (L <= upid && upid <= R)
				add(upid);

		}
		while (nup > q[i].dfn) {
			int upid = upda[nup].c, updd = upda[nup].p;
			if (L <= upid && upid <= R)
				del(upid);
			a[upid] = upda[nup].before;
			if (L <= upid && upid <= R)
				add(upid);
			nup--;
		}
		ans[q[i].id] = answer;

	}
	for (int i = 1; i <= qcn; i++) {
		cout << ans[i] << endl;
	}
}