求助带修莫队+hash储存TLE QAQ #2 #8

#include<bits/stdc++.h>
#define N 100005
#define M 30000005
using namespace std;
int n,m,i,j,cmp,l=1,r,rt,cntq,cntc,u[M],rem[M],a[N],ans[N];
char c;
struct qwq{
	int l,r,t,x,p;
	bool operator < (const qwq &A) const{
		return l/cmp==A.l/cmp?r/cmp==A.r/cmp?t<A.t:r<A.r:l<A.l;
	}
}d[N];
struct awa{
	int w,a;
}q[N];
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x*f;
}
inline int haxi(int n){
	int k=n%M;
	while(u[k] && u[k]!=n) if(++k==M) k=0;
	u[k]=n;
	return k;
}
inline void add(int n){
	rem[haxi(a[n])]++;
}
inline void del(int n){
	rem[haxi(a[n])]--;
}
inline void upd(int n){
	if(q[n].w>=l && q[n].w<=r){
		del(q[n].w);
		rem[haxi(q[n].a)]++;
	}
	swap(a[q[n].w],q[n].a);
}
int main(){
	n=read(),m=read();
	cmp=pow(n,0.666);
	for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=m;i++){
		c=getchar();
		while(c!='Q' && c!='C') c=getchar();
		if(c=='Q'){
			d[++cntq].l=max(read(),1),d[cntq].r=min(read(),n),d[cntq].x=read();
			d[cntq].t=cntc,d[cntq].p=cntq;
		}
		else 
			q[++cntc].w=read(),q[cntc].a=read();
		
	}
	sort(d+1,d+1+cntq);
	for(i=1;i<=cntq;i++){
		while(l<d[i].l) del(l++);
		while(l>d[i].l) add(--l);
		while(r<d[i].r) add(++r);
		while(r>d[i].r) del(r--);
		while(rt<d[i].t) upd(++rt);
		while(rt>d[i].t) upd(rt--);
		ans[d[i].p]=rem[haxi(d[i].x)];
	}
	for(i=1;i<=cntq;i++) printf("%d\n",ans[i]);
	return 0;
}