SQRT Decomposition

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

const int MAXN = 2e5 + 5;
int a[MAXN], n, blockSz;
vector<int> blocks[450];

void build() {
    blockSz = max(1, (int)sqrt(n));
    for (int i = 0; i < n; i++)
        blocks[i / blockSz].push_back(a[i]);
    for (int i = 0; i <= n / blockSz; i++)
        sort(blocks[i].begin(), blocks[i].end());
}

void update(int idx, int val) {
    int bi = idx / blockSz;
    auto &blk = blocks[bi];
    blk.erase(lower_bound(blk.begin(), blk.end(), a[idx]));
    a[idx] = val;
    blk.insert(lower_bound(blk.begin(), blk.end(), val), val);
}

int query(int l, int r, int x) {
    int res = 0;
    while (l <= r && l % blockSz != 0)
        res += a[l++] >= x;
    while (l + blockSz - 1 <= r) {
        auto &blk = blocks[l / blockSz];
        res += blk.end() - lower_bound(blk.begin(), blk.end(), x);
        l += blockSz;
    }
    while (l <= r)
        res += a[l++] >= x;
    return res;
}