Skip to main content

扫描线

参考资料​

例题​

洛谷 P5490 【模板】扫描线 & 矩形面积并

求 nn 个四边平行于坐标轴的矩形的面积并。（n≤105,0≤x,y≤109n\le10^5,0\le x,y\le10^9）

Code (1)
#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=200005;
struct Node
{
	int l,r,h,op;
	bool operator<(const Node &x) const{return h<x.h;}
}node[N];
int a[N],val[N<<2],cnt[N<<2];
void push_up(int u,int l,int r)
{
	if(cnt[u])val[u]=a[r+1]-a[l];
	else if(l==r)val[u]=0;
	else val[u]=val[ls]+val[rs];
}
void update(int u,int l,int r,int x,int y,int v)
{
	if(x<=l&&r<=y)
	{
		cnt[u]+=v;
		push_up(u,l,r);
		return;
	}
	if(x<=mid)update(ls,l,mid,x,y,v);
	if(y>mid)update(rs,mid+1,r,x,y,v);
	push_up(u,l,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		node[++m]={x1,x2,y1,1};a[m]=x1;
		node[++m]={x1,x2,y2,-1};a[m]=x2;
	}
	sort(node+1,node+m+1);
	sort(a+1,a+m+1);
	m=unique(a+1,a+m+1)-a-1;
	ll ans=0;
	for(int i=1;i<=n<<1;i++)
	{
		int l=lower_bound(a+1,a+m+1,node[i].l)-a;
		int r=lower_bound(a+1,a+m+1,node[i].r)-a;
		update(1,1,m,l,r-1,node[i].op);
		ans+=(ll)val[1]*(node[i+1].h-node[i].h);
	}
	cout<<ans<<'\n';
	return 0;
}
洛谷 P10814 【模板】离线二维数点

给你一个长为 nn 的序列 aa，有 mm 次询问，每次询问给定 l,r,xl,r,x，求 [l,r][l,r] 区间中小于等于 xx 的元素个数。

Solution

题意简述​

给定长度为 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) 单点修改和区间查询。

参考代码​

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