scanning line(扫描线)

1.1扫描线的思想以及在几何问题上的应用(eg1,3)

二维数点

平面上有n个点(xi,yi)。

回答q个询问，每个询问给定一个矩形[X1,X2]×[Y1,Y2]，询问矩形里面有多少个点。

因为有1e9的范围，我们离散化一下，我们只关心顺序，不关心具体是多少

这里相当于只需要把原来的点的坐标离散化，查询的时候直接二分找到小于等于他的第一个坐标即可。

思想：

①扫描线+容斥

②离线

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
vector<int>vx;
vector<array<int,4>>event;;
int n,q,m;
int a[N],ans[N];
int c[N];
int query(int x){//1...x
	ll s = 0;
	for(;x;x-=x&(-x))
		s += c[x];
	return s;
}
void modify(int x,int s){//a[x]+=s
	for(;x<=m;x+=x&(-x))
		c[x]+=s;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		vx.push_back(x);
		//y坐标，类型,x坐标
		event.push_back({y,0,x});
	}
	for(int i = 1;i<=q;i++)
	{
		int x1,x2,y1,y2;
		cin>>x1>>x2>>y1>>y2;
		//用容斥
		//y坐标，类型1-,2+,x坐标,哪一个询问
		//0,1,2的设置其实还包含了希望哪个事件先发生,坐标一样的话,我们希望先插入再查询
		event.push_back({y2,2,x2,i});
		event.push_back({y1-1,2,x1-1,i});
		event.push_back({y2,1,x1-1,i});
		event.push_back({y1-1,1,x2,i});
	}
	sort(event.begin(), event.end());
	sort(vx.begin(), vx.end());
	//去重
	vx.erase(unique(vx.begin(), vx.end()),vx.end());
	m = vx.size();
	for(auto evt:event)
	{
		if(evt[1]==0){//插入
			int y = lower_bound(vx.begin(), vx.end(),evt[2])-vx.begin()+1;//树状数组是1base的
			modify(y,1);
		}
		else{//查询<=它的最后一个位置，即第一个>它的位置-1
			int y = upper_bound(vx.begin(), vx.end(),evt[2])-vx.begin()-1+1;//树状数组是1base的
			int tmp = query(y);
			if(evt[1]==1)ans[evt[3]] -= tmp;
			else ans[evt[3]] += tmp;
		}
	}
	for(int i = 1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

矩形面积并

矩形面积并

思路：

x坐标离散化

cnt>0覆盖，cnt=0未被覆盖

用线段树记录cnt的最小值，也就是被覆盖次数的最小的段。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
vector<int>vx;
vector<array<int,4>>event;;
int n,q,m;

struct info
{
	int minv,mincnt;
};

info operator+(const info &l,const info &r)
{
	info a;
	a.minv = min(l.minv,r.minv);
	if(l.minv==r.minv)a.mincnt = l.mincnt + r.mincnt;
	else if(l.minv<r.minv)a.mincnt = l.mincnt;
	else a.mincnt = r.mincnt;
	return a;
}

struct node{
	int t;
	info val;
}seg[N*8];

void update(int id)
{
	seg[id].val = seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,int t)
{
	seg[id].val.minv = seg[id].val.minv+t;
	seg[id].t = seg[id].t + t;
}

void pushdown(int id)
{
	if(seg[id].t!=0)
	{
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t = 0;
	}
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].val = {0,vx[r]-vx[r-1]};
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void modify(int id,int l,int r,int x,int y,ll t){
	if(l==x&&r==y)
	{
		settag(id,t);
		return;
	}
	int mid = (l+r)/2;
	pushdown(id);
	if(y<=mid) modify(id*2,l,mid,x,y,t);
	else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
	else{
		modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
	}
	update(id);
}


int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		int x1,x2,y1,y2;
		cin>>x1>>x2>>y1>>y2;
		vx.push_back(x1);
		vx.push_back(x2);
		//y坐标,类型0,x坐标
		event.push_back({y1,1,x1,x2});
		event.push_back({y2,-1,x1,x2});
	}
	sort(event.begin(), event.end());
	sort(vx.begin(), vx.end());
	//去重
	vx.erase(unique(vx.begin(), vx.end()),vx.end());
	m = vx.size()-1;//段数=点数-1
	build(1,1,m);
	int prey = 0;
	int totlen = seg[1].val.mincnt;
	ll ans = 0;
	for(auto evt:event)
	{
		int cov = totlen;
		if(seg[1].val.minv==0)
			cov = totlen - seg[1].val.mincnt;
		ans += (ll)(evt[0]-prey)*cov;
		prey = evt[0];
		int x1 = lower_bound(vx.begin(), vx.end(),evt[2])-vx.begin()+1;
		int x2 = lower_bound(vx.begin(), vx.end(),evt[3])-vx.begin();
		if(x1>x2)continue;
		modify(1,1,m,x1,x2,evt[1]);
	}
	cout<<ans<<endl;
	return 0;
}

1.2 扫描线在序列问题上的应用(eg2)

区间不同数之和

有\(n\)个数\(a1,a2,…,an\)。

有\(q\)组询问，每次给一个区间\([l,r]\)，求区间里不同的数字之和，也就是说同一个数字出现多次只算一次。

思路：

①思路一：\(pri[i]\)表示\(a[i]\)上一次出现的位置(只统计第一次出现)

\(pri[i]<l\)和\(l<=i<=r\)满足这两个条件的\(ai\)之和。

转化为二维数点问题，所有限制是两维的都可以看成二维数点。

把一个点坐标看成\((i,pri[i])\),$$\begin{cases} pri[i]<l\\ l<=i<=r \end{cases} \tag{1} $$满足这两个条件的\(ai\)之和。

②思路二：for(r = 1~n)

维护\(ans[l] ：[l,r]\)的答案

\(r-1——>r\) , \(ans[l]:[l,r-1]——>[l,r]\)

\(a_r\)在\([l,r-1]\)未出现，\(ans[l]+=a_r\)，否则不变
比如对于\([l,r]\)一段，在\([l,p]\)上\(a_r\)出现过，在\([p+1,r]\)上没出现过，那么\(ans[p+1\)~\(r]+=a[r]\)

综上所述：我们要实现①区间加②单点查询

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
ll n,q,a[N],pos[N],ans[N];
vector<array<int,3>>qu[N];
ll c[N];
ll query(int x){//1...x
	ll s = 0;
	for(;x;x-=x&(-x))
		s += c[x];
	return s;
}
void modify(int x,ll s){//a[x]+=s
	for(;x<=n;x+=x&(-x))
		c[x]+=s;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];

	for(int i = 1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		qu[r].push_back({l,i});
	}
	for(int r = 1;r<=n;r++)
	{
		int p = pos[a[r]];
		modify(p+1,a[r]);
		modify(r+1,-a[r]);
		pos[a[r]] = r;
		for(auto que:qu[r])
		{
			//ans[l]:[l,r]的答案
			ans[que[1]] = query(que[0]);
		}
	}
	for(int i = 1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

2.权值线段树之字典树(eg4)

异或第k小

给\(n\)个数字\(a1,a2,…,an\)。

你要回答\(m\)个询问，每次给定两个数\(x,k\)询问a1 xor x,a2 xor x,…,an xor x中从小到大排序中第\(k\)小的元素。


#include<bits/stdc++.h>
using namespace std;
const int N = 201000;
const int M = 30;//0~2^30-1
int n,m,a[N];

struct node
{
	int s[2];
	int sz;
}seg[N*32];
int tot = 0,root;

int main()
{
	cin>>n>>m;
	root = ++tot;
	for(int i = 0;i<n;i++)
	{
		int x;
		cin>>x;
		int p = root;
		for(int j = M-1;j>=0;j--)
		{
			seg[p].sz+=1;
			int w = (x>>j)&1;
			if(seg[p].s[w]==0)seg[p].s[w] = ++tot;
			p = seg[p].s[w];
		}
		seg[p].sz+=1;
	}
	for(int i = 0;i<m;i++)
	{
		int x,k;
		cin>>x>>k;
		int ans = 0;
		int p = root;
		for(int j = M-1;j>=0;j--)
		{
			int w = (x>>j)&1;
			if(seg[seg[p].s[w]].sz>=k)
			{
				p = seg[p].s[w];
			}else{
				k -= seg[seg[p].s[w]].sz;
				ans^=1<<j;
				p = seg[p].s[w^1];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

3.扫描线与权值线段树的总和运用(eg5)

mex

有一个长度为\(n\)的数组 \(a1,a2,…,an\)。

你要回答\(q\)个询问，每次给一个区间\([l,r]\)，询问这个区间内最小没有出现过的自然数。

for(r = 1~n)

\(posx:\)x最后一次出现的位置，最小的x满足pos[x]<l

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
ll n,q,a[N],pos[N],ans[N];
vector<array<int,3>>qu[N];
struct node{
	int val;
}seg[N*4];

void update(int id)
{
	seg[id].val = min(seg[id*2].val,seg[id*2+1].val);
}


void change(int id,int l,int r,int pos,int val){
	if(l==r)
	{
		seg[id].val = val;
		return;
	}
	int mid = (l+r)/2;
	if(pos<=mid)change(id*2,l,mid,pos,val);
	else change(id*2+1,mid+1,r,pos,val);
	update(id);
}

int search(int id,int l,int r,int d)
{	
	if(l==r)return l;
	int mid = (l+r)>>1;
	if(seg[id*2].val<d)return search(id*2,l,mid,d);
	else return search(id*2+1,mid+1,r,d);
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i],a[i] = min(a[i],n+1);

	for(int i = 1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		qu[r].push_back({l,i});
	}
	for(int r = 1;r<=n;r++)
	{
		//posx :x最后一次出现的位置，
		//最小的x满足pos[x]<l
		//pos[a[r]] = r;
		change(1,0,n+1,a[r],r);
		for(auto que:qu[r])
		{
			ans[que[1]] = search(1,0,n+1,que[0]);
		}
	}
	for(int i = 1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据
• 数据可视化是如何帮助我们高效了解数据的？

扫描线 数据结构 scanning 结构 数据扫描线 数据结构scanning结构 数据结构 数据结构 结构 数据 数据结构 算法 结构 数据 数据结构 结构 笔记 数据 数据结构 结构 数据 大学 数据结构 队列 结构 数据 数据结构 结构 代码 数据 数据结构 索引 结构 数据 结构 数据结构 数据