Warning: session_start(): open(/tmp/sess_70713c0d563c0faa584ce63237394697, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 扫描线问题 ======
===== 例 1 =====
==== 题意 ====
[[https://www.luogu.com.cn/problem/P5490|P5490 【模板】扫描线]]
求 $n$ 个矩形的面积并
==== 题解 ====
此问题可抽象出一个问题模型：
给一初始全 0 的序列 $\{a_i\}_{i=1}^n$，每次操作如下：给定区间 $[l,r]$，令 $a_i=a_i+1,\forall i\in [l,r]$ 或 $a_i=a_i-1,\forall i\in [l,r]$，修改后立即询问 $\#\{a_i|a_i>0,i\in[1,n]\}$，保证任一修改后 $a_i\ge 0,\forall i\in[1,n]$
#include
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
#define ls o<<1
#define rs o<<1|1
ll X[MAXN<<1];
// 横线
struct Line{
// 左右端点的横坐标,竖坐标
ll l,r,h;
// 1 表示下底边，-1 表示上底边
int mark;
// 按高度排序
bool operator < (const Line &rhs) const {
return h>1;
Build(ls,l,mid);
Build(rs,mid+1,r);
return;
}
void Update(int o,int nl,int nr,int c){
int l=t[o].l,r=t[o].r;
if(nl<=l&&r<=nr){
t[o].sum+=c;
Pull(o);
return;
}
int mid=(l+r)>>1;
if(nl<=mid)
Update(ls,nl,nr,c);
if(nr>mid)
Update(rs,nl,nr,c);
Pull(o);
}
}tree;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++){
ll X1,X2,Y1,Y2;
cin>>X1>>Y1>>X2>>Y2;
X[2*i-1]=X1,X[2*i]=X2;
L[2*i-1]=(Line){X1,X2,Y1,1};
L[2*i]=(Line){X1,X2,Y2,-1};
}
n<<=1;
sort(L+1,L+n+1);
sort(X+1,X+n+1);
int tot=unique(X+1,X+n+1)-X-1;
tree.Build(1,1,tot-1);
ll ans=0;
for(int i=1;i