Link to this code:
https://cses.fi/paste/0a9e64569ff00963b92ace/#include <bits/stdc++.h>
using namespace std;
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define el '\n'
#define mod 1000000007
#define MOD2 998244353
#define INF numeric_limits<int>::max()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define popFront(a) a.erase(a.begin())
#define m(a, b) make_pair(a, b)
#define pb push_back
#define ppb pop_back
#define ff [0]
#define ss [1]
#define int long long int
#define yes cout<<"YES"
#define no cout<<"NO"
typedef long double lld;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <pair <int, int> > vll;
typedef pair <int, int> pll;
typedef priority_queue<int> pqi;
typedef priority_queue<int, vector<int>, greater<int> > rpqi;
typedef map<int,int> mi;
typedef map<int,int,greater<int> > rmi;
typedef map<char,int> mc;
#ifndef ONLINE_JUDGE
#define debug(a) cerr << #a <<" "; _print(a); cerr << el;
#else
#define debug(a)
#endif
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }
template <class T, class V> void _print(pair<T, V> p);
template <class T> void _print(vector<T> v);
template <class T> void _print(set<T> v);
template <class T, class V> void _print(map<T, V> v);
template <class T> void _print(multiset<T> v);
int f[100005];
template <class T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map<T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p[0] >> p[1]); }
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; }
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p[0] << " " << p[1] << el); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
unsigned int GCD(int v, int b) {if (b > v) {return GCD(b, v);} if (b == 0) {return v;} return GCD(b, v % b);}
int LCM(int v, int b) { return (v / GCD(v, b)) * b; }
int pwr(int v, int b, int mods) {int res = 1; while (b > 0) {if (b & 1)res = (res * v) % mods; v = (v * v) % mods; b = b >> 1;} return res;}
int mminvprime(int v, int b) {return pwr(v, b - 2, b);}
int modAdd(int v, int b, int m) {v = v % m; b = b % m; return (((v + b) % m) + m) % m;}
int modMul(int v, int b, int m) {v = v % m; b = b % m; return (((v * b) % m) + m) % m;}
int modSub(int v, int b, int m) {v = v % m; b = b % m; return (((v - b) % m) + m) % m;}
string printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} return s;}
int modDiv(int v, int b, int m) {v = v % m; b = b % m; return (modMul(v, mminvprime(b, m), m) + m) % m;} //only for prime m
int ncr(int n,int r,int p){return (f[n]*mminvprime(f[r],p)%p*mminvprime(f[n-r],p)%p)%p;}
bool isPrime(int n) { if(n < 2) return false; for(int k = 2; k * k <= n; k++) if(n % k == 0) return false; return true; }
void factorial(){f[0]=1;for(int i=1;i<=1e5;i++) f[i]=modMul(f[i-1],i,mod);}
int n,m,q;
const int N = 10000005;
// int grid[1001][1001];
int seg[4*N];
int bucket[N];
// int lazy[4*N];
int arr[200001];
unordered_map<int,int>mp;
int ans;
int hl(int i){
return i*100+1;
}
int hr(int i){
return (i+1)*100;
}
int querytree(int idx,int l,int r,int a,int b){
int x = hl(l);
int y = hr(r);
if(x>b||y<a) return 0;
if(x>=a&&y<=b){
return seg[idx];
}
if(l==r){
int ans = 0;
for(int i=x;i<=y;i++){
if(i>=a&&i<=b) ans+=mp[i];
}
return ans;
}
int mid = (l+r)/2;
int left = querytree(2*idx+1,l,mid,a,b);
int right = querytree(2*idx+2,mid+1,r,a,b);
return left+right;
}
void update(int idx,int l,int r,int i){
if(l==r){
seg[idx]-=1;
return;
}
int mid = (l+r)/2;
int left = hl(l);
int right = hr(mid);
if(i>=left&&i<=right) update(2*idx+1,l,mid,i);
else update(2*idx+2,mid+1,r,i);
seg[idx]=seg[2*idx+1]+seg[2*idx+2];
}
void update2(int idx,int l,int r,int i){
if(l==r){
seg[idx]+=1;
return;
}
int mid = (l+r)/2;
int left = hl(l);
int right = hr(mid);
if(i>=left&&i<=right) update2(2*idx+1,l,mid,i);
else update2(2*idx+2,mid+1,r,i);
seg[idx]=seg[2*idx+1]+seg[2*idx+2];
}
void buildtree(int idx,int l,int r){
if(l==r){
seg[idx]=bucket[l];
return;
}
int mid = (l+r)/2;
buildtree(2*idx+1,l,mid);
buildtree(2*idx+2,mid+1,r);
seg[idx]=seg[2*idx+1]+seg[2*idx+2];
}
void solve(){
cin>>n>>q;
for(int i=0;i<n;i++){
int x; cin>>x;
arr[i]=x;
mp[x]++;
int temp = arr[i]/100;
if(arr[i]%100) temp--;
bucket[temp]++;
}
buildtree(0,0,1e7);
for(int i=0;i<q;i++){
char x; cin>>x;
if(x=='?'){
int a,b; cin>>a>>b;
cout<<querytree(0,0,1e7,a,b)<<endl;
}else{
int a,b; cin>>a>>b;
update(0,0,1e7,arr[a-1]);
update2(0,0,1e7,b);
mp[arr[a-1]]--;
mp[b]++;
arr[a-1]=b;
}
}
}
signed main()
{
FastIO;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// #define _DEBUG
#ifdef _DEBUG
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int tt = clock();
#endif
int t = 1, i = 1;
// cin >> t;
// factorial();
while (t--)
{
// cout<<"Case #"<<i++<<": ";
solve();
cout << el;
}
// solve();
#ifdef _DEBUG
cerr << "TIME = " << (float)(clock() - tt) / CLOCKS_PER_SEC << endl;
tt = clock();
#endif
} 