Shared code

/**
 *    author: tourist
 *    created: 22.05.2025 16:24:14
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <typename T>
class fenwick {
 public:
  vector<T> fenw;
  int n;

  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }

  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr); 
  int n, q;
  cin >> n >> q;
  vector<int> x(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
  }
  vector<pair<int, int>> sx(n + 1);
  for (int i = 1; i <= n; i++) {
    sx[i] = make_pair(x[i], i);
  }
  sort(sx.begin(), sx.end());
  vector<tuple<int, int, int, int>> events;
  for (int i = 0; i < q; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    events.emplace_back(d, b, 1, i);
    events.emplace_back(c - 1, a - 1, 1, i);
    events.emplace_back(d, a - 1, -1, i);
    events.emplace_back(c - 1, b, -1, i);
  }
  sort(events.begin(), events.end());
  fenwick<int> fenw(n + 1);
  int ptr = 1;
  vector<int> ans(q);
  for (auto [v, i, sig, id] : events) {
    while (ptr <= n && sx[ptr].first <= v) {
      fenw.modify(sx[ptr].second, 1);
      ptr += 1;
    }
    ans[id] += sig * fenw.get(i);
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}