题解 | 换个角度思考

Modern Cpp

树状数组写法

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

template<typename T>
struct Fenwick {
  int n;
  std::vector<T> tr;

  Fenwick(int n) : n(n), tr(n + 1, 0) {}

  int lowbit(int x) {
    return x & -x;
  }

  void modify(int x, T c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
  }

  T query(int x) {
    T res = T();
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
  }

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

using BIT = Fenwick<int>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n, m;
  std::cin >> n >> m;

  std::vector<std::array<int, 2>> a(n + 1);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i][0];
    a[i][1] = i;
  }

  std::sort(a.begin() + 1, a.end());

  std::vector<std::array<int, 4>> query(m);
  for(int i = 0; i < m; i++){
    for(int j = 0; j < 3; j++){
      std::cin >> query[i][j];
    }
    query[i][3] = i;
  }

  std::sort(query.begin(), query.end(), [&](const auto& t1, const auto& t2){
    return t1[2] < t2[2];
  });

  BIT bit(n);
  std::vector<int> ans(m);
  int cur = 1;
  for(int i = 0; i < m; i++){
    int v = query[i][2];
    while(cur <= n && a[cur][0] <= v){
      bit.modify(a[cur][1], 1);
      cur++;
    }
    ans[query[i][3]] = bit.query(query[i][0], query[i][1]);
  }

  for(int i = 0; i < m; i++){
    std::cout << ans[i] << "\n";
  }

  return 0;
}