Shared code

#include<bits/stdc++.h>
using namespace std;
void update_seg(int idx, vector<int>&seg, int low, int high, int val, int change){
    if(val < low || val > high)return;
    seg[idx] += change;
    if(low >= high)return;
    int mid = low + (high - low)/2;
    update_seg(2*idx+1, seg, low, mid, val, change );
    update_seg(2*idx+2, seg,  mid+1, high, val, change);
}
int query_seg(int idx, vector<int>&seg, int low, int high, int ql, int qr){
    if(low > qr || high < ql )return 0;
    if(low >= ql && high <= qr)return seg[idx];
    int mid = low + (high - low)/2;
    int left = query_seg(2*idx+1, seg, low , mid, ql, qr);
    int right = query_seg(2*idx+2, seg, mid+1, high, ql, qr);
    return left + right;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin>>n>>q;
    set<int>st;
    vector<int>p(n);
    for(int i = 0;i<n;i++){
        cin>>p[i];
        st.insert(p[i]);
    }
    vector<vector<int>>query(q);
    for(int i = 0;i<q;i++){
        char type;
        cin>>type;
        int a, b;
        cin>>a>>b;
        st.insert(a), st.insert(b);
        query[i] = {(type == '!'), a, b};
    }
    map<int, int>mp;
    int cur=  0;
    for(int i : st){
        mp[i] = cur++;
    }
    int total = int(mp.size());
    vector<int>seg(4*total);
    for(int i = 0;i<n;i++){
        update_seg(0, seg, 0, total-1, mp[p[i]], 1);
    }
    for(int i = 0;i<q;i++){
        if(query[i][0] == 1){
            int k = query[i][1];
            int x = query[i][2];
            update_seg(0, seg, 0, total-1, mp[p[k-1]], -1);
            p[k-1] = x;
            update_seg(0, seg, 0, total-1, mp[x], 1);
        }else{
            int l = query[i][1], r= query[i][2];
            int res = query_seg(0, seg, 0, total-1, mp[l], mp[r]);
            cout<<res<<"\n";
        }
    }
}