Shared code

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

struct fenwick {
    int n;
    vector<int> tree;

    fenwick(int _n) : n(_n+10), tree(n+50) {}

    void update(int p) {
        for(p++; p<n; p+=p&-p) tree[p]++;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }

    int query(int l, int r) {
        return query(r) - query(l-1);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n >> q;
    set<int> st;
    vector<int> a(n+1);

    for(int i=1; i<=n; i++) {
        cin >> a[i];
        st.insert(a[i]);
    }

    vector<array<int, 4> > in[n+1];
    for(int i=1; i<=q; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        in[x1-1].push_back({ x2, y2, -1, i });
        in[y1].push_back({ x2, y2, 1, i });
        st.insert(x2);
        st.insert(y2);
    }

    vector<int> comp( st.begin(), st.end() );
    int m = comp.size();

    fenwick fwt(m);
    vector<int> ans(q+1);

    auto lb = [&](int x) {
        return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
    };

    for(int i=1; i<=n; i++) {
        fwt.update(lb(a[i]));
        for(auto &[l, r, c, id] : in[i])
            ans[id] += fwt.query( lb(l), lb(r) ) * c;
    }

    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}