扫描线
luckydrawbox
·
·
个人记录
这里提供求矩形面积并的扫描线。
你可以根据自己的需要更改基本数据类型 S\_B\_T：
#define S_B_T long long
上面实现了一个以 long long 为基本数据类型的定义。
所有的函数已经完成，所以你只需要用到两个函数：
$\text{ask\_area}()$：求此时的矩形面积并。
```cpp
#define pl p<<1
#define pr p<<1|1
#define S_B_T long long
struct Scanning_Beam{
int tot;
vector<S_B_T>y_set;
struct Tree{
int l,r;
S_B_T len,cnt;
}a[8*N];
struct Line{
S_B_T x,y1,y2,k;
bool operator<(const Line &a)const{
return x<a.x;
}
}b[2*N],e;
Scanning_Beam(){
tot=0;
}
int find(S_B_T y){
return lower_bound(y_set.begin(),y_set.end(),y)-y_set.begin();
}
void pushup(int p){
if(a[p].cnt)
a[p].len=y_set[a[p].r+1]-y_set[a[p].l];
else if(a[p].l^a[p].r)
a[p].len=a[pl].len+a[pr].len;
else
a[p].len=0;
}
void build(int p,int l,int r){
a[p].l=l;a[p].r=r;
a[p].len=a[p].cnt=0;
if(l==r)
return;
int mid=l+r>>1;
build(pl,l,mid);
build(pr,mid+1,r);
pushup(p);
}
void modify(int p,int l,int r,S_B_T x){
if(l<=a[p].l&&a[p].r<=r){
a[p].cnt+=x;
pushup(p);
return;
}
int mid=a[p].l+a[p].r>>1;
if(l<=mid)
modify(pl,l,r,x);
if(r>mid)
modify(pr,l,r,x);
pushup(p);
}
void add(S_B_T x,S_B_T y1,S_B_T y2,S_B_T k){
e.x=x;e.y1=y1;
e.y2=y2;e.k=k;
b[tot++]=e;
}
void insert(S_B_T x1,S_B_T y1,S_B_T x2,S_B_T y2){
add(x1,y1,y2,1);
add(x2,y1,y2,-1);
y_set.push_back(y1);
y_set.push_back(y2);
}
S_B_T ask_area(){
S_B_T ans=0;
sort(y_set.begin(),y_set.end());
y_set.erase(unique(y_set.begin(),y_set.end()),y_set.end());
build(1,0,y_set.size()-2);
sort(b,b+tot);
for(int i=0;i<tot;i++){
if(i)
ans+=a[1].len*(b[i].x-b[i-1].x);
modify(1,find(b[i].y1),find(b[i].y2)-1,b[i].k);
}
return ans;
}
}tree;
```
空间复杂度 $O(10N)$，$\text{insert}$ 操作时间复杂度为 $O(1)$，$\text{ask\_area}$ 操作时间复杂度为 $O(n\log n)$。