#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=5e5+10;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>s[N];
map<int,int>mp;int trlen,a[N];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(!mp[a[i]])mp[a[i]]=++trlen;
		s[mp[a[i]]].insert(i);
	}
	while(q--)
	{
		int op;cin>>op;
		if(op==0)
		{
			int x,y;cin>>x>>y;x++;
			s[mp[a[x]]].erase(x);
			if(!mp[y])mp[y]=++trlen;
			a[x]=y;
			s[mp[a[x]]].insert(x);
		}
		else
		{
			int l,r,x;cin>>l>>r>>x;l++;
			if(!mp[x]){cout<<0<<'\n';continue;}
			x=mp[x];
			auto it=s[x].lower_bound(l),it1=s[x].upper_bound(r);
			if(it==s[x].end()){cout<<0<<'\n';continue;}
			int num=*it,id=s[x].order_of_key(num);
			if(it1==s[x].end()){cout<<s[x].size()-id<<'\n';continue;}
			int num1=*it1,id1=s[x].order_of_key(num1);
			cout<<id1-id<<'\n';
		}
	}
	return 0;
}

cdq分治太美妙了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,id,p[200010],lsh[600010],ln;
struct N{
	int op,x,y,v,id;
}a[600010];
bool cmp(N a,N b){
	return a.x<b.x;
}
int ans[200010],cnt[600010];
void solve(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(a+l,a+mid+1,cmp);
	sort(a+mid+1,a+r+1,cmp);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&a[j].x<=a[i].x){
			if(a[j].op==0)cnt[a[j].v]+=a[j].y;
			j++;
		}
		if(a[i].op==1)ans[a[i].id]+=cnt[a[i].v]*a[i].y;
	}
	for(int i=l;i<j;i++)if(a[i].op==0)cnt[a[i].v]-=a[i].y;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		a[++id]={0,i,1,p[i],0};
		lsh[++ln]=p[i];
	}
	int qi=0;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		if(op==0){
			int k,v;
			cin>>k>>v;k++;
			lsh[++ln]=v;
			a[++id]={0,k,-1,p[k],0};
			a[++id]={0,k,1,v,0};
			p[k]=v;
		}
		else{
			int l,r,x;
			cin>>l>>r>>x;l++;
			lsh[++ln]=x;
			a[++id]={1,r,1,x,++qi};
			if(l>1)a[++id]={1,l-1,-1,x,qi};
		}
	}
	sort(lsh+1,lsh+1+ln);
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=id;i++)a[i].v=lower_bound(lsh+1,lsh+1+ln,a[i].v)-lsh;
	solve(1,id);
	for(int i=1;i<=qi;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}