Shared code

#include<bits/stdc++.h>

#define lli long long int
#define MOD 1000000007

using namespace std;

lli gcd(lli a, lli b);
lli binary_exp(lli a, lli b, lli mod);

class BIT{
	private:
		map<lli, lli> bit;
		lli size;
	public:
		BIT(lli n){
			size = n+1;
		}
		void update(lli idx, lli val){
			lli cur = idx + 1;
			while(cur < size){
				bit[cur] += val;
				cur += cur&(-cur);
			}
		}
		// returns [0, index] inclusive
		lli query(lli index){
			lli cur = index+1;
			lli res = 0;
			while(cur > 0){
				res += bit[cur];
				cur -= cur&(-cur);
			}
			return res;
		}

};

void solve(){
	lli n, q; cin >> n >> q;
	vector<lli> salary(n);
	for(int i=0;i<n;i++){
		cin >> salary[i];
	}
	lli MAX_VAL = 1000000000;
	BIT ft(MAX_VAL);
	for(int i=0;i<n;i++){
		ft.update(salary[i], 1);
	}
	while(q--){
		char com; cin >> com;
		if(com == '?'){
			lli a, b; cin >> a >> b;
			cout <<  ft.query(b) - ft.query(a-1) << endl;
		}
		else{
			lli k, x; cin >> k >> x;
			k--;
			ft.update(salary[k], -1);
			salary[k] = x;
			ft.update(salary[k], 1);
		}
	}
}

bool multitestcase = false;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testCase = 1;
	if(multitestcase) cin >> testCase;
	while(testCase--){
		solve();
	}
	return 0;
}

lli gcd(lli a,lli b) {
	if(b == 0) return a;
	return gcd(b, a%b);
}

lli binary_exp(lli a, lli b, lli mod){
	lli res = 1;
	while(b > 0){
		if(b&1){
			res = (res*a)%mod;
		}
		a = (a*a)%mod;
		b = b/2;
	}
	return res;
}