TLE on#5

#include <bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int, int>
#define ls(k) z[k].son[L]
#define rs(k) z[k].son[R]
#define lson ls(k), l, mid
#define rson rs(k), mid + 1, r
#define ui unsigned int
#define ull unsigned long long
#define lb lower_bound 
#define rb upper_bound 
#define mii map<int, int>
#define mll map<ll, ll>
#define mset multiset
#define low(k) (k) & (-(k))
using namespace std;
typedef long long ll;
const int L = 0, R = 1;
const int N = 2e6 + 10;
struct node{
	int x, y, pos;
}z[N * 5];
int x1_[N], y1_[N], x2_[N], y2_[N], tot[N], ans[6][N];
int c[N * 5], b[N * 5];
int n, m, q;
inline void modify(const int& k,const int& d){
	for(int i = k; i <= n; i += low(i))
		c[i] += d;
}
inline int query(const int& k){
	int ret = 0;
	for(int i = k; i; i -= low(i))
		ret += c[i];
	return ret;
}
inline bool cmp(const node& a, const node& b){
	if(a.x != b.x)
		return a.x < b.x;
	else if(a.y != b.y)
		return a.y < b.y;
	else
		return a.pos < b.pos;
}
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		x = (x<<3)+(x<<1)+(ch^'0');
		ch = getchar();
	}
	return x * f;
}
inline void write(int x)
{
  if(x < 0)
    putchar('-'),x = -x;
  if(x > 9)
    write(x / 10);
  putchar(x % 10 + '0');
  return;
}
int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; ++i){
		z[i].x = i, z[i].y = read();
		z[i].pos = 0;
	}
	for(int i = 1; i <= m; ++i){
		x1_[i] = read(),  x2_[i] = read(), y1_[i] = 0, y2_[i] = read();
	  z[++n].x = x2_[i], z[n].y = y2_[i], z[n].pos = i;
	  z[++n].x = x1_[i] - 1, z[n].y = y2_[i], z[n].pos = i;
	  z[++n].x = x2_[i], z[n].y = y1_[i] - 1, z[n].pos = i;
	  z[++n].x = x1_[i] - 1, z[n].y = y1_[i] - 1, z[n].pos = i;
	}
	sort(z + 1, z + n + 1, cmp);
	for(int i = 1; i <= n; ++i)
		b[i] = z[i].y;
	sort(b + 1, b + 1 + n);
	q = unique(b + 1, b + 1 + n) - b - 1;
	for(int i = 1; i <= n; ++i){
		int id = lb(b + 1, b + q + 1, z[i].y) - b;
		if(z[i].pos)
			ans[++tot[z[i].pos]][z[i].pos] = query(id);
		else 
			modify(id, 1);
	}
	for(int i = 1; i <= m; ++i)
		write(ans[4][i] - ans[3][i] - ans[2][i] +ans[1][i]), cout << '\n';
	return 0;
}