带修莫队80求条

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200005],to[200005];
struct node{int l,r,x,t,id;}b[200005];
struct nod{int a,p;}c[200005];
inline bool cmp(const node &p,const node &q){
	if(to[p.l]!=to[q.l])return p.l<q.l;
	if(to[p.r]!=to[q.r])return p.r<q.r;
	return p.t<q.t;
}
unordered_map<int,int>mp;
inline void chang(int &p,int &L,int &R){
	int pos=c[p].a,to=c[p].p;
	if(pos>=L&&pos<=R){
		mp[a[pos]]--;
		mp[to]++;
	}
	swap(c[p].p,a[pos]);
}
inline void add(int &p){mp[a[p]]++;}
inline void del(int &p){mp[a[p]]--;}
int ans[200005];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	int N=pow(n,2.0/3.0);
	for(int i=1;i<=n;i++)cin>>a[i],to[i]=(i-1)/N+1;
	int time=0;
	for(int i=1;i<=m;i++){
		char op;int l,r,x;
		cin>>op>>l>>r;
		if(op=='Q')cin>>b[i-time].x,b[i-time].l=l,b[i-time].r=r,b[i-time].t=time,b[i-time].id=i-time;
		else c[++time].a=l,c[time].p=r;
	}
	sort(b+1,b+1+m-time,cmp);
	int l=1,r=0,t=0;
	for(int i=1;i<=m-time;i++){
		int L=b[i].l,R=b[i].r,T=b[i].t;
		while(l>L)add(--l);
		while(r<R)add(++r);
		while(l<L)del(l),l++;
		while(r>R)del(r),r--;
		while(t<T)chang(++t,l,r);
		while(t>T)chang(t,l,r),t--;
		ans[b[i].id]=mp[b[i].x];
	}
	for(int i=1;i<=m-time;i++)cout<<ans[i]<<'\n';
	return 0;
}