P10814 【模板】离线二维数点

题意简述

给定长度为 $n$ 的序列 $a$，有 $m$ 次询问。

每次询问给定 $l,r,x$，求区间 $[l,r]$ 中满足 $a_i\le x$ 的元素数量。

解题思路

思想

每个元素 $a_i$ 可以看作二维平面中的一个点 $(i,a_i)$。

每次询问 $(l,r,x)$ 等价于统计矩形 $[l,r]\times[1,x]$ 内点的数量。

直接二维数据结构会超时，考虑转化为可以 前缀查询 的一维问题。

差分

每次询问是可差分的，区间 $[l,r]$ 可以拆分为 $[1,r]-[1,l-1]$。

这样每次询问转化为 $2$ 个 前缀询问 $(u,x)$：统计区间 $[1,u]$ 中满足 $a_j\le x$ 的元素数量。

统计

将所有 $2m$ 个前缀询问按第一维 $u$ 排序。

用序列 $b$ 维护值域，$b_k$ 表示当前第二维为 $k$ 的元素数量。

对于每个前缀询问 $(u,x)$，先将所有 $j\le u$ 的 $a_j$ 加入序列 $b$，得到前缀 $[1,u]$ 的状态。

计算 $s=\sum_{k=1}^x b_k$ 表示当前满足 $a_j\le x$ 的元素数量，最后将 $s$ 贡献到对应问题的答案。

使用 树状数组 维护序列 $b$，实现 $O(\log n)$ 单点修改和区间查询。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=2000005;
int a[N],c[N],ans[N];
void add(int u){while(u<N){c[u]++;u+=u&-u;}}
int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<tuple<int,int,int,int>> s;
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		cin>>l>>r>>x;
		s.push_back({r,x,i,1});
		s.push_back({l-1,x,i,-1});
	}
	sort(s.begin(),s.end());
	int j=1;
	for(auto [u,x,i,f]:s)
	{
		while(j<=u)add(a[j++]);
		ans[i]+=sum(x)*f;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}