Shared code

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

#define MAX 212345
#define LOG 20
#define PI acos(-1.)
#define MAXG 1123
#define INF 1123456789
#define INFLL 112345678911234567
#define EPS 1e-9
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int n, m, k, arr[MAX];

#define lft(u) ((u) << 1)
#define rgt(u) (lft(u) + 1)

vector<int> st[2 * MAX];

void build() {
    for(int i = n; i < (n << 1); i++) {
        st[i] = {arr[i - n]};
    }
    for(int i = n - 1; i > 0; i--) {
        merge(st[lft(i)].begin(), st[lft(i)].end(),
              st[rgt(i)].begin(), st[rgt(i)].end(),
              back_inserter(st[i])
        );
    }
}

int countRange(int l, int r, int x, int y) {
    int ans = 0;
    for(l += n, r += n; l <= r; ++l >>= 1, --r >>= 1) {
        if((l & 1) == 1) ans += upper_bound(st[l].begin(), st[l].end(), y) - lower_bound(st[l].begin(), st[l].end(), x);
        if((r & 1) == 0) ans += upper_bound(st[r].begin(), st[r].end(), y) - lower_bound(st[r].begin(), st[r].end(), x);
    }
    return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c, t, u, v, w, f, q, ans;
	ll la, lb, lc, lans;
    string s1, s2;
    char ch1, ch2;
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    build();
    while(q--) {
        cin >> a >> b >> u >> v;
        a--; b--;
        cout << countRange(a, b, u, v) << '\n';
    }
    return 0;
}