【算法模板】离线树状数组(区间查询小于等于x的数个数)

只需要把询问按x升序排序，在查询的过程中不断让树状数组把<=x元素的下标处+1即可。（为此，把序列按val排序）

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10;  pair<int, int> a[N]; #define val first #define pos second  struct query {     int l, r, x, pos, ans; } q[N];  int n, m;  struct BIT {     int t[N];     BIT() { memset(t, 0, sizeof(t)); }     void add(int i, int x) {         for (; i <= n; i += i & -i)             t[i] += x;     }     int sum(int i) {         int res = 0;         for (; i; i -= i & -i)             res += t[i];         return res;     } };  int main() {     ios::sync_with_stdio(false);      cin.tie(0);     cin >> n >> m;     for (int i = 1; i <= n; i++) {         cin >> a[i].val;         a[i].pos = i;     }     for (int i = 1; i <= m; i++) {         cin >> q[i].l >> q[i].r >> q[i].x;         q[i].pos = i; q[i].ans = 0;     }     sort(a + 1, a + 1 + n);     sort(q + 1, q + 1 + m, [&](query a, query b) { return a.x < b.x; });          BIT T; int p = 0;     for (int i = 1; i <= m; i++) {         query& Q = q[i];         while (a[p + 1].val <= Q.x && p + 1 <= n) {             p++;             T.add(a[p].pos, 1);         }         Q.ans = T.sum(Q.r) - T.sum(Q.l - 1);     }     sort(q + 1, q + 1 + m, [&](query a, query b) { return a.pos < b.pos; });     for (int i = 1; i <= m; i++)         cout << q[i].ans << \n;     return 0; }