专栏文章

题解：P10814 【模板】离线二维数点

llailai0916qwq
P10814题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min04rx1
此快照首次捕获于
2025/12/01 18:23
3 个月前
此快照最后确认于
2025/12/01 18:23
3 个月前
查看原文

题意简述

给定长度为 nn 的序列 aa，有 mm 次询问。
每次询问给定 l,r,xl,r,x，求区间 [l,r][l,r] 中满足 ai≤xa_i\le x 的元素数量。

解题思路

思想

每个元素 aia_i 可以看作二维平面中的一个点 (i,ai)(i,a_i)。
每次询问 (l,r,x)(l,r,x) 等价于统计矩形 [l,r]×[1,x][l,r]\times[1,x] 内点的数量。
直接二维数据结构会超时，考虑转化为可以 前缀查询 的一维问题。

差分

每次询问是可差分的，区间 [l,r][l,r] 可以拆分为 [1,r]−[1,l−1][1,r]-[1,l-1]。
这样每次询问转化为 22 个 前缀询问 (u,x)(u,x)：统计区间 [1,u][1,u] 中满足 aj≤xa_j\le x 的元素数量。

统计

将所有 2m2m 个前缀询问按第一维 uu 排序。
用序列 bb 维护值域，bkb_k 表示当前第二维为 kk 的元素数量。
对于每个前缀询问 (u,x)(u,x)，先将所有 j≤uj\le u 的 aja_j 加入序列 bb，得到前缀 [1,u][1,u] 的状态。
计算 s=∑k=1xbks=\sum_{k=1}^x b_k 表示当前满足 aj≤xa_j\le x 的元素数量，最后将 ss 贡献到对应问题的答案。
使用 树状数组 维护序列 bb，实现 O(log⁡n)O(\log n) 单点修改和区间查询。

参考代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...