Super Mario

给定一个长度为n的区间，同时给出m个询问，每次询问在区间[l,r]中有多少个数小于或等于k。

总是莫名MLE调了半天了。。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (int)l;i <= (int)r;i++)
#define per(i,r,l) for(int i = (int)r;i >= (int)l;i--)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define mp make_pair
#define SZ(a) (int)(a.size())
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef double db;

const int N = 100000 + 10,inf = 1e9,mod = inf + 7, M = 30;

int n, q;
int a[N], sum[N*M], root[N], ls[N*M], rs[N*M], idx, m;
VI num;

int build(int l, int r) {
	int id = ++idx;
	if (l < r) {
		int mid = (l + r) >> 1;
		ls[idx] = build(l, mid);
		rs[idx] = build(mid + 1, r);
	}
	return id;
}

int change(int id, int l, int r, int x) {
	int t = ++idx;
	ls[t] = ls[id], rs[t] = rs[id], sum[t] = sum[id] + 1;
	if (l == r) return t;
	int mid = (l + r) >> 1;
	if (x <= mid)
		ls[t] = change(ls[id], l, mid, x);
	else
		rs[t] = change(rs[id], mid + 1, r, x);
	return t;
}

int query(int id, int l, int r, int x, int y) {
	if (x <= l && r <= y)
		return sum[id];
	int mid = (l + r) >> 1, res = 0;
	if (x <= mid) res += query(ls[id], l, mid, x, y);
	if (y > mid) res += query(rs[id], mid + 1, r, x, y);
	return res;
}

inline void read (int &X){
	X = 0;int w = 0; char ch = 0;
	while (!isdigit (ch)) {w |= ch == '-'; ch = getchar  ();}
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar ();
	if (w) X = -X;
}

int main() {
	int T;
	scanf("%d", &T);
	rep(t,1,T) {
		memset(sum, 0, sizeof sum);
		memset(ls, 0, sizeof ls);
		memset(rs, 0, sizeof rs);
		idx = 0;
		num.clear();
		//初始化
		read(n); read(q);
		rep(i,1,n) {
			read(a[i]);
			num.pb(a[i]);
		}
		sort(all(num));
		num.erase(unique(all(num)), num.end());
		int m = num.size();
		root[0] = build(1, m);
		rep(i,1,n) {
			int xb = lower_bound(all(num), a[i]) - num.begin() + 1;
			root[i] = change(root[i - 1], 1, m, xb);
		}
		printf("Case %d:\n", t);
		while (q--) {
			int l, r, k;
			read(l); read(r); read(k);
			r++;
			int xb = upper_bound(all(num), k) - num.begin();
			int res = query(root[r], 1, m, 1, xb);
			res -= query(root[l], 1, m, 1, xb);
			printf("%d\n", res);
		}
		fflush(stdin);
	}
	return 0;
}