扫描线
PPT讲的好简洁啊,我已经不会概括了。感谢smr学长留下的宝贵PPT的(´▽`ʃ♡ƪ)
引用内容是 PTT 原话,不会变成全文引用吧……
算法简介
有一些扫描线的本质上的理解:大致就是把原题的限制是 B 维正交范围。
- 定义:在一个 $B$ 维直角坐标系下,第 $i$ 维坐标在一个整数范围 $[L_i,R_i]$间,内部的点集。
这个有些抽象,但一般我们只关注一维和二维的情况,三维或者四维就需要强上数据结构嵌套了。(或者 CDQ 嵌套)
然后呢以二维平面举例。
表面上:我们通过排序排掉一维,用数据结构维护另一维。那么扫描线体现在哪呢?
实际上:我们通过排序排掉了一维,从左往右遍历就是扫描线。数据结构只是维护扫描线移动时另一维的修改于查询。
- 对于一个静态的二维问题,我们可以使用扫描线扫一维,数据结构维护另一维。
同时维护也有技巧:如果能差分就差分,不能就需要分治。
以上是对普遍的扫描线思想的理解,当然也有更具体的理解:
另一种看待问题的角度是站在序列角度,而不站在二维平面角度。
如果我们这样看待问题,则扫描线实际上是枚举了右端点 $r=1\to n$,维护一个数据结构,支持查询
对于当前的 $r$,给定一个值 $l$,$l$ 到 $r$ 的答案是什么。
即扫描线扫询问右端点,数据结构维护所有左端点的答案。
这两种理解都可以,因为就目前而言,扫描线的题一般都在二维平面上。很少有高维偏序强堆码量的(吧?)
具体做法
如果能差分,就直接差分最好。有如下差分方式:
- 序列区间 $[l,r]$ 差分为 $[1,r]−[1,l−1]$ 的两个前缀。
- 树上差分。
- 二维前缀和的差分。
差分的作用可以将一维直接消掉,使得原问题降一维。
差分可以解决“自由度”的问题。
因为通过差分我们可以将一个高维问题以常数的代价转换为低维问题。
而问题低一维往往会简单非常多。所以建议大家做题看到可以差分的区间,树路径等范围,想都不想直接差分掉。
【模板】离线二维数点
扫描线模板题,离线询问,按 $r$ 升序,另一维权值树状数组即可。
如果是 $[x,y]$ 呢?差分即可。
#include<bits/stdc++.h>
#define ll long long
#define lowbit(i) i&-i
using namespace std;
const int N=2e6+10;
int tr[N];
int n,m,a[N];
struct node{
int x,id,v;
};
int ans[N];
vector<node> vec[N];
void update(int x,int k){
for(int i=x;i<=N-10;i+=lowbit(i)){
tr[i]+=k;
}
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
int main(){
#ifdef LOCAL
freopen("D:/Desktop/cpp/data/code.in","r",stdin);
freopen("D:/Desktop/cpp/data/code.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int l,r,x;
cin>>l>>r>>x;
vec[l-1].push_back({x,i,-1});
vec[r].push_back({x,i,1});
}
for(int i=1;i<=n;i++){
update(a[i],1);
for(node tmp:vec[i]){
ans[tmp.id]+=tmp.v*query(tmp.x);
}
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
例题2
给一个二维平面,上面有 $n$ 个矩形,每个矩形坐标范围 $[1,n]$。
有 $m$ 次查询,每次查询一个二维平面上的点被多少矩形包含。
矩形的左边界赋 1 ,右边界赋 -1。我们就维护了 $x$ 轴方向上的点被多少个矩形覆盖。
再拿数据结构维护一下 $y$ 轴即可。维护 $y$ 轴的时候记得差分一下。
反演
简单而言,区间询问每个元素的情况,可以转化为每个元素对区间的贡献。
具体来说将区间的询问变成二维平面上面的每一个点,将每一个元素贡献的区间变成有贡献的矩形,最
后跑一遍扫描线求值即可。由于我们把询问区间元素转化成了询问元素对哪些区间有贡献,索性把这种方法称为反演。
HH的项链
按照古早的思想,发现性质:贡献会在倒数第二次出现的数上,直接维护这个即可。
但我们现在换个角度考虑问题:
假设我们现在右端点是 $r$,那么当我们扫到 $r+1$ 时,会新增一个数 $y=a_{r+1}$ ,假设 $y$ 上次出现的位置是 $x$,那么 $x+1\to r+1$ 的位置就会新增一个贡献,进行一个区间加法。然后差分转为 单点加和区间查 即可。
One Occurrence
这道题我们使用二维平面的方法分析,也就是将区间和每一个位置进行反演。
思路就是将询问区间 $[l,r]$ 看做是二维平面上的一个点,然后计算序列中每个位置对哪些询问有贡献。
之后变成先进行一些矩形加,后进行一些单点求值的问题。我们对序列中每个位置计算后,会发现问题变为 $O(n)$ 次矩形加。
之后每个询问的点就是一次单点的值,使用扫描线+树状数组即可,总时间复杂度 $O((n+m)\log n)$。
上述是 PPT 的题解,是纯种的扫描线。题解区没有树状数组,只有线段树和主席树
但是,众所周知,莫队也是扫描线,所以我们可以用莫队给这题*飞。
直接值域分块+莫队,add 和 del 是自然的。虽然我 add 写挂了二十分钟没查出来吧
#include<bits/stdc++.h>
#define ll long long
#define B 1025
using namespace std;
const int N = 5e5+10;
int n,a[N],m,cnt[N],ans[N];
struct node{
int l,r,id;
bool operator < (const node &a)const{
return (l/B==a.l/B) ? ((l/B)&1) ? r<a.r : r>a.r : l/B<a.l/B;
}
}q[N];
int l=1,r=0;
int sum[5005],bel[N],tot,L[5005],R[5005];
void add(int x){
if(cnt[a[x]]==1) sum[bel[a[x]]]--;
if(cnt[a[x]]==0) sum[bel[a[x]]]++;
cnt[a[x]]++;
}
void del(int x){
if(cnt[a[x]]==1) sum[bel[a[x]]]--;
if(cnt[a[x]]==2) sum[bel[a[x]]]++;
cnt[a[x]]--;
}
void init(){
tot=(N-11)/B+1;
for(int i=1;i<=N-10;i++){
bel[i]=(i-1)/B+1;
}
for(int i=1;i<=tot;i++){
L[i]=(i-1)*B+1;
R[i]=min(i*B,N-10);
}
}
int query(){
for(int i=tot;i>=1;i--){
if(!sum[i]) continue;
for(int j=R[i];j>=L[i];j--) if(cnt[j]==1) return j;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
init();
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+1+m);
for(int i=1;i<=m;i++){
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(r>q[i].r) del(r--);
ans[q[i].id]=query();
}
for(int i=1;i<=m;i++){
cout << ans[i] << '\n';
}
return 0;
}
还有,本题说的卡常,随手加个奇偶化排序就过了,这算啥卡常啊。
后面的操作太超模了,先【TBD】了。