Shared code

/*
    AUTHOR -> KIMJONGOOF (CODEFORCES)
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int mod = 1e9 + 7;
const int inf = 1e18;
const int K = 26;
/*
 __builtin_popcountll(x): Counts the number of one’s(set bits) in an integer(long/long long).
 __builtin_parityll(x): Checks the Parity of a number.Returns true(1) if the number has odd parity(odd number of set bits) else it returns false(0) for even parity(even number of set bits).
 __builtin_clzll(x): Counts the leading number of zeros of the integer(long/long long).
 __builtin_ctzll(x): Counts the trailing number of zeros of the integer(long/long long).
cout << fixed << setprecision(x) << ans << "\n"; : Use this in case ans is required upto x deciaml precision
kuch nai sooj rha? binary search try kiya ??
*/

// Normal segment tree without lazy propagation..

struct node
{
    // node e ki ki thakbe bhabho bhalo kore!!
    int sum;
    node()
    {
        sum = 0;
    }
};

node merge(node a, node b)
{
    // nodes er merge korar logic ki?
    //  kokhono xor koro kokhono min-max to kokhono sum and so on..
    node ans;
    ans.sum = a.sum + b.sum;
    return ans;
}

vector<node> t;
vector<int> cnt;

void build(int id, int l, int r)
{
    if (l == r)
    {
        // Eita kintu leaf node
        // initializing logic set korte hobe eikhane
        t[id].sum = cnt[l];
        return;
    }
    // tarpor to shudu O(logn) e shob update hobe..
    int mid = (l + r) >> 1;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    t[id] = merge(t[2 * id], t[2 * id + 1]);
}

void update(int id, int l, int r, int pos, int val)
{
    if (pos < l || pos > r)
    {
        // eikhane kono overlap hobe na
        // kichu korte hobe na
        return;
    }

    if (l == r)
    {
        // mane amra pos index e pohuche gachi eibaar shudu update koro ar tarpor return!!
        t[id].sum += val;
        return;
    }

    // tarpor to as usual (Ologn) e update koro..
    int mid = (l + r) >> 1;
    update(2 * id, l, mid, pos, val);
    update(2 * id + 1, mid + 1, r, pos, val);
    t[id] = merge(t[2 * id], t[2 * id + 1]);
}

node query(int id, int l, int r, int lo, int hi)
{
    if (lo > r || l > hi)
    {
        // thik ager moton eikhane o kono overlap nei, to kichu korte hobe na
        return node(); // eita kintu shob shomaye thik na, just sum er case e thik
        // ei case e ki return hobe sheita bhabte hobe..
    }

    if (lo <= l && hi >= r)
    {
        // again ager moton eikhane puro overlao hoche, so just return the entire node
        return t[id];
    }

    int mid = (l + r) >> 1;
    return merge(query(2 * id, l, mid, lo, hi), query(2 * id + 1, mid + 1, r, lo, hi));
}

int n, q;
vector<int> a, stor;
vector<vector<int>> queries;
int get_val(vector<int> &a, int val)
{
    int ind = lower_bound(a.begin(), a.end(), val) - a.begin();
    return ind;
}
void solve()
{
    cin >> n >> q;
    a.assign(n, 0);
    stor.clear();
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        stor.push_back(a[i]);
    }

    while (q--)
    {
        char tt;
        int aa, b;
        cin >> tt >> aa >> b;
        queries.push_back({tt == '!', aa, b});
        stor.push_back(aa);
        stor.push_back(b);
    }

    sort(stor.begin(), stor.end());
    stor.erase(unique(stor.begin(), stor.end()), stor.end());

    int sz = stor.size();
    cnt.assign(sz, 0);
    for (auto it : a)
    {
        cnt[get_val(stor, it)]++;
    }

    t.assign(4 * sz, node());
    build(1, 0, sz - 1);

    for (auto it : queries)
    {
        if (it[0] == 1)
        {
            int nval = get_val(stor, a[it[1] - 1]);
            update(1, 0, sz - 1, nval, -1);
            a[it[1] - 1] = it[2];
            update(1, 0, sz - 1, get_val(stor, it[2]), 1);
        }
        else
        {
            cout << query(1, 0, sz - 1, get_val(stor, it[1]), get_val(stor, it[2])).sum << "\n";
        }
    }

    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _;
    for (int __ = 1; __ <= _; __++)
    {
        solve();
    }
}