非修改莫队是对的

修改莫队核心代码如下：

while(t < q[i].t)
		{
			t++;
			if(r[t].p >= L && r[t].p <= R)
			{
				add(r[t].c, num);
				del(a[r[t].p], num);
			}
			swap(r[t].c, a[r[t].p]);
		}
		while(t > q[i].t)
		{
			if(r[t].p >= L && r[t].p <= R)
			{
				add(r[t].c, num);
				del(a[r[t].p], num);
			}
			swap(r[t].c, a[r[t].p]);
			t--;
		}

完整代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, m;
int a[N], cnt[N], ans[N];
int len;
int qcnt, rcnt;
struct Query
{
	int id, l, r, t;
}q[N];

struct Replace
{
	int p, c;
}r[N];

void add(int x, int &num)
{
	cnt[a[x]]++;
	if(cnt[a[x]])
		num++;
}

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

bool cmp(Query x, Query y)
{
	if(x.l / len != y.l / len)
		return x.l / len < y.l / len;
	else if(x.r / len != y.r / len)
		return x.r / len < y.r / len;
	else
		return x.t < y.t;
}

signed main()
{
	cin >> n >> m;
	len = pow(n, (2.0 / 3.0));
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++)
	{
		char op;
		cin >> op;
		if(op == 'Q')
		{
			cin >> q[++qcnt].l >> q[qcnt].r;
			q[qcnt].id = qcnt;
			q[qcnt].t = rcnt;
		}
		else
		{
			cin >> r[++rcnt].p >> r[rcnt].c;			
		}
	}
	sort(q + 1, q + qcnt + 1, cmp);
	int L, R, num, t;
	L = R = num = t = 0;
	for(int i = 1; i <= qcnt ; i++)
	{
		while(L < q[i].l) del(L++, num);
		while(L > q[i].l) add(--L, num);
		while(R < q[i].r) add(++R, num);
		while(R > q[i].r) del(R--, num);
		while(t < q[i].t)
		{
			t++;
			if(r[t].p >= L && r[t].p <= R)
			{
				add(r[t].c, num);
				del(a[r[t].p], num);
			}
			swap(r[t].c, a[r[t].p]);
		}
		while(t > q[i].t)
		{
			if(r[t].p >= L && r[t].p <= R)
			{
				add(r[t].c, num);
				del(a[r[t].p], num);
			}
			swap(r[t].c, a[r[t].p]);
			t--;
		}
		ans[q[i].id] = num;
	}
	for(int i = 1; i <= qcnt; i++)
		cout << ans[i] << endl;
	return 0;
}