Shared code

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define int long long
 
const char nl = '\n';
const int N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9+7;

int a[N], b[N], c[N], d[N];

struct segtree {
	vector<int> tree;
	int size;
	
	void init(int n) {
		size = 1;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, 0);
	}
	
	void add(int i, int x, int lx, int rx) {
		if (rx-lx ==1) {
			tree[x] += 1;
			return;
		}
		
		int mid = lx+rx>>1;
		if (i < mid)add(i, 2*x+1, lx, mid);
		else add(i, 2*x+2, mid, rx);
		tree[x] = tree[2*x+1]+tree[2*x+2];
	}
	
	void add(int i) {
		add(i, 0, 0, size);
	}
	
	int get(int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx)return 0;
		if (lx >= l && rx <= r)return tree[x];
		int mid = lx+rx>>1;
		return get(l, r, 2*x+1, lx, mid)+get(l, r, 2*x+2, mid, rx);
	}
	
	int get(int l, int r) {
		return get(l, r, 0, 0, size);
	}
};

int32_t main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	
	int n, q; cin >> n >> q;
	
	map<int, int> mp, mp2;
	vector<int> arr(n);
	for (auto &i: arr) {
		cin >> i;
		mp[i] += 1;
	}
	
	for (int i = 0; i < q; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		--a[i], --b[i];
		mp[c[i]] += 1, mp[d[i]] += 1;
	}
	
	int time = 0;
	for (auto i: mp)
		mp2[i.first] = time++;
		
	for (auto &i: arr) {
		i = mp2[i];
	}
	
	vector<int> ans(q);
	
	vector<tuple<int, int>> g[n+1];
	for (int i = 0; i < q; ++i) {
		c[i] = mp2[c[i]], d[i] = mp2[d[i]];
		//cout << nl << c[i] << " " << d[i] << nl; 
		if (a[i] != 0) {
			g[a[i]-1].push_back({-1, i});
		}
		g[b[i]].push_back({1, i});
	}
	
	segtree st;
	st.init(sz(mp)+1);
	
	for (int i = 0; i < n; ++i) {
		st.add(arr[i]);
		for (auto j: g[i]) {
			int x, y;
			tie(x, y) = j;
			ans[y] += st.get(c[y], d[y]+1)*x;
		}
	}
	
	for (auto i: ans)cout << i << nl; 
	return 0;
}
 
// biconnected components
// matching algorithm
// lambda's optimization