扫描线

参考资料

• 扫描线 - OI Wiki

例题

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

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

求 $n$ 个四边平行于坐标轴的矩形的面积并。（$n\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 【模板】离线二维数点

洛谷 P10814 【模板】离线二维数点

给你一个长为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问给定 $l,r,x$，求 $[l,r]$ 区间中小于等于 $x$ 的元素个数。

Solution

题意简述

给定长度为 $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;
}