线段树进阶
线段树分治
P5787
判断二分图可以用扩展域并查集，采用线段树分治，线段树上的每一个结点作为每一段时间。
每个结点上的修改和回溯需要用到可撤销的并查集。
时间复杂度 \(O(n\log k \log n)\)
扫描线
扫描线求矩形面积
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int x[N];
struct node1{
int xa,xb,y,type;
}line[N];
struct node2{
int l,r;
ll sum;
int cnt;
}tree[N<<3];
bool cmp1(int x,int y){
return x < y;
}
bool cmp2(node1 x,node1 y){
return x.y < y.y;
}
void build(int p,int l,int r){
tree[p].l = x[l];
tree[p].r = x[r];
if(r-l<=1){
return;
}
int mid = (l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid,r);
}
void update(int p){
if(tree[p].cnt){
tree[p].sum = tree[p].r - tree[p].l;
}else{
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
}
void add(int p,int l,int r,int c){
if(l <= tree[p].l && r >= tree[p].r){
tree[p].cnt += c;
update(p);
return;
}
if(l < tree[p<<1].r){
add(p<<1,l,r,c);
}
if(r > tree[p<<1|1].l){
add(p<<1|1,l,r,c);
}
update(p);
}
int main(){
int n;
ll ans = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int xa,xb,ya,yb;
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
x[i] = xa;
x[i+n] = xb;
line[i] = (node1){xa,xb,ya,1};
line[i+n] = (node1){xa,xb,yb,-1};
}
n <<= 1;
sort(x+1,x+1+n,cmp1);
sort(line+1,line+1+n,cmp2);
build(1,1,n);
for(int i=1;i<=n;i++){
ans += tree[1].sum * (line[i].y - line[i-1].y);
add(1,line[i].xa,line[i].xb,line[i].type);
}
printf("%lld",ans);
}
扫描线求矩形周长
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int x[N];
struct node1{
int xa,xb,y,type;
}line[N];
struct node2{
int l,r,sum,cnt;
int t;
bool lc,rc;
}tree[N<<3];
bool cmp1(int x,int y){
return x < y;
}
bool cmp2(node1 x,node1 y){
return x.y == y.y ? x.type > y.type : x.y < y.y;
}
void build(int p,int l,int r){
tree[p].l = x[l];
tree[p].r = x[r];
if(r-l<=1){
return;
}
int mid = (l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid,r);
}
void update(int p){
if(tree[p].cnt){
tree[p].sum = tree[p].r - tree[p].l;
tree[p].lc = true;
tree[p].rc = true;
tree[p].t = 2;
}else{
tree[p].lc = tree[p<<1].lc;
tree[p].rc = tree[p<<1|1].rc;
tree[p].t = tree[p<<1].t + tree[p<<1|1].t;
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
if(tree[p<<1].rc && tree[p<<1|1].lc){
tree[p].t -= 2;
}
}
}
void add(int p,int l,int r,int c){
if(l <= tree[p].l && r >= tree[p].r){
tree[p].cnt += c;
update(p);
return;
}
if(l < tree[p<<1].r){
add(p<<1,l,r,c);
}
if(r > tree[p<<1|1].l){
add(p<<1|1,l,r,c);
}
update(p);
}
int main(){
int n,ans = 0,last = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int xa,xb,ya,yb;
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
x[i] = xa;
x[i+n] = xb;
line[i] = (node1){xa,xb,ya,1};
line[i+n] = (node1){xa,xb,yb,-1};
}
n <<= 1;
sort(x+1,x+1+n,cmp1);
sort(line+1,line+1+n,cmp2);
build(1,1,n);
for(int i=1;i<=n;i++){
add(1,line[i].xa,line[i].xb,line[i].type);
ans += abs(last-tree[1].sum);
last = tree[1].sum;
ans += tree[1].t*(line[i+1].y - line[i].y);
}
printf("%d",ans);
}