我的代码时间轴上单次修改应该是 $O(1)$ 的，然而 T 了几个点，而且好像超时很多。

这是为什么呢？

#include<bits/stdc++.h>
using namespace std;
int n, m, qn, cn, kc, ks, c[140005], cc[140005], kl[3005], kr[3005], cnt[1000005];
struct que{
	int l, r, t, id;
	int ans;
}q[140005];
struct chg{
	int x, pc, nc, id;
}ch[140005];
int find(int x){
	int l = 0, r = cn, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (x > ch[mid].id)
			ans = mid, l = mid + 1;
		else
			r = mid - 1;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> c[i];
		cc[i] = c[i];
	}
	for (int i = 1; i <= m; i++){
		char op;
		cin >> op;
		if (op == 'Q'){
			qn++;
			cin >> q[qn].l >> q[qn].r;
			q[qn].id = i;
		}else if (op == 'R'){
			cn++;
			cin >> ch[cn].x >> ch[cn].nc;
			ch[cn].id = i;
		}
	}
	for (int i = 1; i <= cn; i++){
		ch[i].pc = cc[ch[i].x];
		cc[ch[i].x] = ch[i].nc;
	}
	sort(q + 1, q + qn + 1, [](que a, que b){return a.l < b.l;});
	kc = pow(qn, 0.666) + 1, ks = ceil(qn * 1.00 / kc) + 0.114514;
	for (int i = 1; i <= ks; i++){
		kl[i] = kc * (i - 1) + 1;
	}
	kl[ks + 1] = qn + 1;
	for (int i = 1; i <= qn; i++)
		q[i].t = find(q[i].id);
	for (int i = 1; i <= ks; i++)
		sort(q + kl[i], q + kl[i + 1], [](que a, que b){return a.r != b.r ? a.r < b.r : a.t < b.t;});
	for (int i = 1; i <= ks; i++){
		int ans = 0;
		for (int j = 1; j <= n; j++)
			cc[j] = c[j];
		memset(cnt, 0, sizeof cnt);
		for (int j = 1; j <= q[kl[i]].t; j++)
			cc[ch[j].x] = ch[j].nc;
		for (int j = q[kl[i]].l; j <= q[kl[i]].r; j++){
			if (cnt[cc[j]] == 0)
				ans++;
			cnt[cc[j]]++;
		}
		q[kl[i]].ans = ans;
		for (int j = kl[i] + 1; j < kl[i + 1]; j++){
			if (q[j].t > q[j - 1].t)
				for (int k = q[j - 1].t + 1; k <= q[j].t; k++){
					cc[ch[k].x] = ch[k].nc;
					if (!(ch[k].x >= q[j - 1].l && ch[k].x <= q[j - 1].r))
						continue;
					if (cnt[ch[k].pc] == 1)
						ans--;
					cnt[ch[k].pc]--;
					if (cnt[ch[k].nc] == 0)
						ans++;
					cnt[ch[k].nc]++;
				}
			else
				for (int k = q[j - 1].t; k > q[j].t; k--){
					cc[ch[k].x] = ch[k].pc;
					if (!(ch[k].x >= q[j - 1].l && ch[k].x <= q[j - 1].r))
						continue;
					if (cnt[ch[k].pc] == 0)
						ans++;
					cnt[ch[k].pc]++;
					if (cnt[ch[k].nc] == 1)
						ans--;
					cnt[ch[k].nc]--;
				}
			if (q[j].l > q[j - 1].l)
				for (int k = q[j - 1].l; k < q[j].l; k++){
					if (cnt[cc[k]] == 1)
						ans--;
					cnt[cc[k]]--;
				}
			else
				for (int k = q[j].l; k < q[j - 1].l; k++){
					if (cnt[cc[k]] == 0)
						ans++;
					cnt[cc[k]]++;
				}
			for (int k = q[j - 1].r + 1; k <= q[j].r; k++){
				if (cnt[cc[k]] == 0)
					ans++;
				cnt[cc[k]]++;
			}
			q[j].ans = ans;
		}
	}
	sort(q + 1, q + 1 + qn, [](que a, que b){return a.id < b.id;});
	for (int i = 1; i <= qn; i++)
		cout << q[i].ans << "\n";
	return 0;
}