Shared code

#include<bits/stdc++.h>
using namespace std;

#define N 10000001
	
int n, m;
map<int,int> salary2freq;
int freq100[N], slry[N];
int seg[4*N];

void init(){
	for(int i=0; i<N; i++){
		freq100[i] = 0;
		slry[i] = 0;
	}
}

void build(int l=0, int r=N-1, int j=0){
	if(l==r){
		seg[j] = freq100[l];
		return;
	}

	int mid = (l+r)/2;
	build(l,mid,2*j+1);
	build(mid+1,r,2*j+2);
	seg[j] = seg[2*j+1]+seg[2*j+2];
}

void update(int ka, int kr, int l=0, int r=N-1, int j=0){
	// cout << ka << " " << kr << " " << l << " " << r << " " << endl;
	if(l==r){
		if(ka!=-1){
			freq100[l]++;
			seg[j] = freq100[l];
		}
		if(kr!=-1){
			freq100[l]--;
			seg[j] = freq100[l];
		}
		// cout << ka << " " << kr << " " << l << " " << r << " " << seg[j] << " " << endl;
		return;
	}

	int mid = (l+r)/2;
	if(ka <= mid){
		if(kr <= mid){
			update(ka, kr, l, mid, 2*j+1);
		}else{
			update(ka, -1, l, mid, 2*j+1);
			update(-1, kr, mid+1, r, 2*j+2);
		}
	}else{
		if(kr <= mid){
			update(-1, kr, l, mid, 2*j+1);
			update(ka, -1, mid+1, r, 2*j+2);
		}else{
			update(ka, kr, mid+1, r, 2*j+2);
		}
	}

	seg[j] = seg[2*j+1] + seg[2*j+2];
}

int get(int a, int b, int l=0, int r=N-1, int j=0){
	if(a <= l && r <= b){
		return seg[j];
	}else if(b < l || r < a){
		return 0;
	}else{
		int mid = (l+r)/2;
		return get(a,b,l,mid,2*j+1) + get(a,b,mid+1,r,2*j+2);
	}
}

int calc(int lo, int hi){
	int res = 0;
	map<int,int> :: iterator it;
	it = salary2freq.lower_bound(lo);
	while(it != salary2freq.end() && it->first <= hi){
		res += it->second;
		it++;
	}
	return res;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	init();

	cin >> n >> m;
	int sal;
	for(int i=0; i<n; i++){
		cin >> sal;
		salary2freq[sal]++;
		freq100[sal/100]++;
		slry[i] = sal;
	}

	build();

	while(m--){
		char op; cin >> op;
		int a, b;
		cin >> a >> b;
		if(op == '!'){
			a--;
			int last = slry[a];
			salary2freq[last]--;
			slry[a] = b;
			salary2freq[b]++;
			update(b/100, last/100);
		}else{
			int aa = a/100;
			int bb = b/100;
			int ans = 0;
			ans += get(aa,bb);
			if(aa+1 != bb){
				ans -= calc(aa*100, a-1);
				ans -= calc(b+1, (bb+1)*100-1);
			}
			printf("%d\n", ans);
		}
	}
}