刚学带修莫队求调

#include <bits/stdc++.h>
using namespace std;
int n,m,B;
int tme,tot;
int a[133340];
int b[133340];
int c[1000005];
struct node
{
	int l,r,id,t,ans;
	bool operator<(const node &a)const
	{
		if((l+B-1)/B != (a.l+B-1)/B)
		{
			return (l+B-1)/B < (a.l+B-1)/B;
		}
		if((r+B-1)/B != (a.r+B-1)/B)
		{
			return (r+B-1)/B < (a.r+B-1)/B;
		}
		return t<a.t;
	}
};
bool cmp(node x,node y)
{
	return x.id < y.id;
}
struct rode
{
	int p,cf,cs;
};
node qr[133340];
rode rp[133340];
int l = 1,r = 0,t = 0,ans;
void addr()
{
	r++;
	c[a[r]]++;
	if(c[a[r]] == 1)ans++;
	return;
}
void delr()
{
	c[a[r]]--;
	if(c[a[r]] == 0)ans--;
	r--;
	return;
}
void addl()
{
	l--;
	c[a[l]]++;
	if(c[a[l]] == 1)ans++;
	return;
}
void dell()
{
	c[a[l]]--;
	if(c[a[l]] == 0)ans--;
	l++;
	return;
}
void addt()
{
	t++;
	int p = rp[t].p;
	int cf = rp[t].cf;
	int cs = rp[t].cs;
	if(l <= p <= r)
	{
		c[cf]--;
		if(c[cf] == 0)ans--;
		c[cs]++;
		if(c[cs] == 1)ans++;
	}
	a[p] = cs;
	return;
}
void delt()
{
	int p = rp[t].p;
	int cf = rp[t].cf;
	int cs = rp[t].cs;
	if(l <= p <= r)
	{
		c[cs]--;
		if(c[cs] == 0)ans--;
		c[cf]++;
		if(c[cf] == 1)ans++;
	}
	a[p] = cf;
	t--;
	return;
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		b[i] = a[i]; 
	}
	for(int i = 1;i <= m;i++)
	{
		char op;
		cin >> op;
		if(op == 'Q')
		{
			int l,r;
			cin >> l >> r;
			qr[++tot] = {l,r,tot,tme,0};
		}
		else if(op == 'R')
		{
			int p,c;
			cin >> p >> c;
			rp[++tme] = {p,b[p],c};
			b[p] = c;
		}
	}
	B = cbrt(1ll*n*n);
	sort(qr+1,qr+tot+1);
	for(int i = 1;i <= tot;i++)
	{
		while(r < qr[i].r)addr();
		while(r > qr[i].r)delr();
		while(l > qr[i].l)addl();
		while(l < qr[i].l)dell();
		while(t < qr[i].t)addt();
		while(t > qr[i].t)delt();
		qr[i].ans = ans;
	}
	sort(qr+1,qr+tot+1,cmp);
	for(int i = 1;i <= tot;i++)
	{
		cout << qr[i].ans << "\n";
	}
	return 0;
}