可以参考 P10814 【模板】离线二维数点的数据范围，但是需要在线。

bdfs 无果。已尝试二维树状数组，但是无法开这么大的空间，于是尝试 unordered_map 和字典树维护，但常数都比较大，无法通过。

参考代码（仅能在线通过 $10^5$ 的数据点）。

#include <cstdio>
#include <unordered_map>
int n,m;
std::unordered_map<long long,int>a;
void change(int x,int y,int k){
	for(int i=x;i<=n;i+=(i&-i)){
		for(int j=y;j<=m;j+=(j&-j)){
			long long t=i; t=t<<32; t+=j;
			a[t]+=k;
		}
	}
	return;
}
int ask(int x,int y){
	int ret=0;
	for(int i=x;i>0;i-=(i&-i)){
		for(int j=y;j>0;j-=(j&-j)){
			long long t=i; t=t<<32; t+=j;
			std::unordered_map<long long,int>::iterator it1=a.find(t);
			if(it1!=a.end()){
				ret+=it1->second;
			}
		}
	}
	return ret;
}
int ask(int x1,int y1,int x2,int y2){
	return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
}
int read(){
	int x=0,flag=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') flag=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	if(flag==1) return -x;
	return x;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		int a=read();
		change(i,a,1);
	}
	for(int i=1;i<=m;i++){
		int l=read(),r=read(),x=read();
		printf("%d\n",ask(l,1,r,x));
	}
	return 0;
}