自动搬运

查看原文

来自洛谷，原作者为

	可爱的小棉羊 还不赖！

搬运于2025-08-24 23:01:32，当前版本为作者最后更新于2024-07-29 09:40:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

经典板子。

我们不妨这样理解：

把 $a_i$ 看成平面直角坐标系上的一个点 $(i,a_i)$。

以样例为例：

好的现在我们来看询问是不是在问一个长方形内有多少的点，还是那第一问为例：

答案显然是 $5$。

这个长方形显然是 $[l,r][0,x]$ 的范围。

我们不妨这样想 $[l,r]$ 的点相当于 $[1,r]$ 的点减去 $[1,l-1]$ 的点。

那么我们离线，用一条线从左往右的扫：

每遇到一个点我们把他加入一个集合 $S$，表示当前所有扫到过的点，那么我就要维护 $S$ 内比 $x$ 小的个数，显然的权值线段树或者树状数组。

这样就可以解决问题时间复杂度 $O((n+m)\log m)$

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,id,val;
};
int lowbit(int i){
	return i&(-i);
}
int f[2000005];
void add(int x){
	for(int i=x;i<=2000000;i+=lowbit(i))f[i]++;
}
int ask(int x){
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i))ans+=f[i];
	return ans;
}
vector<node>vec[2000005];
int ans[2000005],n,m,a[2000006];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int l,r,x;
		cin>>l>>r>>x;
		vec[l-1].push_back({x,i,-1});
		vec[r].push_back({x,i,1});
	}
	for(int i=1;i<=n;i++){
		add(a[i]);
		for(int j=0;j<vec[i].size();j++){
			ans[vec[i][j].id]+=vec[i][j].val*ask(vec[i][j].x);
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

这个板子很版，很重要！