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