每日一题：换个角度思考（树状数组）

题意

给定一个长度为 $(1<=n<=1e5)$ 的数组，$(1<=q<=1e5)$ 次询问查询区间 $[l,r]$ 内 $<=k$ 的元素个数。

solution

考虑树状数组。我们在查询区间 $<=k$ 的个数时，为了更好计数，这个区间应该不包含 $>k$ 的元素才行。因此我们不妨离线，将询问的 $k$ 从小到大排序，将数组也从小到大排序，这样从小到大处理询问，每次处理时只将 $<=k$ 的数挂到树的对应下标上（因为询问的 $k$ 是从小到大的，因此之前树上的数一定比当前询问的 $k$ 要小），维护答案为 $query(r) - query(l-1)$。

Code

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 5;

struct Node {
  int l, r, v, id;
} q[N];

int n, m, c[N], res[N];
pair<int, int> p[N];

bool cmp(Node x, Node y) { return x.v < y.v; }

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

int query(int x) {
  int sum = 0;
  for (; x >= 1; x -= x & (-x)) sum += c[x];
  return sum;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].x;
    p[i].y = i;
  }
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= m; i++) {
    cin >> q[i].l >> q[i].r >> q[i].v;
    q[i].id = i;
  }
  sort(q + 1, q + m + 1, cmp);
  int pos = 1;
  for (int i = 1; i <= m; i++) {
    while (q[i].v >= p[pos].x && pos <= n) {
      update(p[pos].y);
      pos++;
    }
    res[q[i].id] = query(q[i].r) - query(q[i].l - 1);
  }
  for (int i = 1; i <= m; i++) cout << res[i] << '\n';
  return 0;
}