区间小于等于k的个数

例题

在给定 N 长的数组 A 中进行 Q 次询问 [Li,Ri] 区间中不大于 Hi 的元素个数

思路

做这个题也是花了很久时间啊，做题看着代码改了一下午加一晚上，中间还做了道分块基础，今早还做不出，中午终于改对，感觉自己蠢爆了

然后讲思路，一般思路都是for套个while，但是这套我还没完全理解，下次更

这里是学习的这位的思路，严格鸽，日更大佬orz

考虑到我们如果暴力的遍历每个区间中的的数，重叠的点被多次访问，浪费了时间。

于是我们换个角度，我们只把每个点遍历一遍，求点对区间的贡献。点对区间的贡献可以用前缀和来做，我们用树状数组动态地做这个前缀和。

要做到这点，我们先对A数组进行离散化。然后将查询的操作按L，R分开来做，一个点如果是L，对区间的贡献乘-1，如果是R就正常加上，这样对于一个查询我们就求出了他的值。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
const int N=5e6+10;
namespace ls { //离散模板
	#define int long long
	const int Nn=5e6+10;
	int C[Nn],L[Nn],A[Nn];
	void ls(int *f,int *a,int n) {
		for(int i=0; i<n; i++)A[i]=a[i+1];
		memcpy(C,A,sizeof(A));
		sort(C,C+n);
		int l=unique(C,C+n)-C;
		//int l=n;
		for(int i=0; i<n; i++) {
			L[i]=lower_bound(C,C+l,A[i])-C+1;
		}
		for(int i=0; i<n; i++)f[i+1]=L[i];
	}
} int n,m;
int L[N],R[N],a[N],H[N],f[N],ans[N],c[N];
struct node {
	int k,x,id;
};
vector<node>g[N];
int lowbit(int x) {
	return (x&(-x));
}
int query(int x) {
	int ret=0;
	while(x>0) {
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
void update(int x,int d) {
	while(x<=n+m) {
		c[x]+=d;
		x+=lowbit(x);
	}
}
signed main() {
	int T;
	cin>>T;
	while(T--) {
		cin>>n>>m;
		memset(c,0,sizeof(c));
		memset(ans,0,sizeof(ans));
		for(int i=1; i<=n; i++)g[i].clear();
		for(int i=1; i<=n; i++)cin>>a[i];
		for(int i=1; i<=m; i++)cin>>L[i]>>R[i]>>a[n+i];
		ls::ls(f,a,n+m);
		for(int i=1; i<=n; i++)a[i]=f[i];
		for(int i=1; i<=m; i++)H[i]=f[n+i];
		for(int i=1; i<=m; i++) {
			g[L[i]-1].push_back({-1,H[i],i});
			g[R[i]].push_back({1,H[i],i});
		}
		for(int i=1; i<=n; i++) {
			update(a[i],1);
			for(auto v:g[i]) {
				ans[v.id]+=v.k*query(v.x);
			}
		}
		for(int i=1; i<=m; i++)cout<<ans[i]<<" ";
		cout<<"\n";
	}

	return 0;
}