↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define endl '\n'↵
const int onee7 = 10000000;↵
const int hundred = 100;↵
ll int t[4*onee7]={0};↵
void build(ll int a[], ll int v,ll int tl, ll int tr) {↵
if (tl == tr) {↵
t[v] = a[tl];↵
} else {↵
ll int tm = (tl + tr) / 2;↵
build(a, v*2, tl, tm);↵
build(a, v*2+1, tm+1, tr);↵
t[v] = t[v*2]+t[v*2+1];↵
}↵
}↵
↵
ll int sumi(ll int v, ll int tl, ll int tr, ll int l, ll int r) {↵
if (l > r) ↵
return 0ll;//changes↵
if (l == tl && r == tr) {↵
return t[v];↵
}↵
ll int tm = (tl + tr) / 2;↵
return sumi(v*2, tl, tm, l, min(r, tm))+sumi(v*2+1, tm+1, tr, max(l, tm+1), r);↵
}↵
void update(ll int v, ll int tl, ll int tr, ll int pos, ll int delta) {↵
if (tl == tr) {↵
t[v] += delta;↵
} else {↵
ll int tm = (tl + tr) / 2;↵
if (pos <= tm)↵
update(v*2, tl, tm, pos, delta);↵
else↵
update(v*2+1, tm+1, tr, pos, delta);↵
t[v] = t[v*2] + t[v*2+1];↵
}↵
}↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll int q,n;↵
cin>>n>>q;↵
ll int arr[n+1];↵
unordered_map<ll int,ll int> umap;↵
umap.reserve(1024);↵
umap.max_load_factor(0.25);↵
for(ll int i=1;i<=n;i++){↵
cin>>arr[i];↵
umap[arr[i]]++;↵
t[onee7+(arr[i]%hundred)]++;↵
}↵
for(int i=onee7-1;i>0;--i) t[i]=t[i<<1]+t[i<<1|1];↵
↵
for(ll int i=0;i<q;i++){↵
char x;↵
cin>>x;↵
if(x=='!'){↵
l
cin>>y>>z;↵
umap[arr[y]]--;↵
update(1,1,onee7,arr[y]%hundred,-1);↵
arr[y]=z;↵
umap[z]++;↵
update(1,1,onee7,arr[y]%hundred,+1);↵
}else{↵
ll int y,z;↵
cin>>y>>z;↵
ll int ans =0;↵
if(z-y<=100){↵
for(ll int k=y;k<=z;k++) ans+=umap[k];↵
}↵
else{↵
ans+=sumi(1,1,onee7,(y%hundred)+1,(z%hundred)-1);↵
for(ll int k = y ; k<((y%100)*100);k++) ans+=umap[k];↵
for(ll int k = (z%100)*100;k<=z;k++) ans+=umap[k];↵
}↵
cout<<ans<<endl;↵
}↵
↵
}↵
return 0;
