这是我扫描线的代码:
#include<iostream>
#include<algorithm>
#define int long long
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 9;
int n;
int c[N << 1];
struct rect{
int x1,y1,x2,y2;
} a[N];
int cnt;
struct node{
int x,y1,y2,k;
} seg[N << 1];
bool cmp(node elem1,node elem2){
return elem1.x < elem2.x;
}
int tmp[N << 1],top;
long long ans;
bool in_range(int l,int r,int L,int R){
return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
return l > R || r < L;
}
struct seg_tree{
int cnt,len;
} t[N << 4];
void push_up(int root,int l,int r){
if(t[root].cnt > 0)
t[root].len = tmp[r + 1] - tmp[l];
else
t[root].len = t[lchild].len + t[rchild].len;
}
void update(int root,int l,int r,int L,int R,int k){
if(out_range(l,r,L,R))
return;
if(in_range(l,r,L,R)){
t[root].cnt += k;
push_up(root,l,r);
return;
}
update(lchild,l,mid,L,R,k);
update(rchild,mid + 1,r,L,R,k);
push_up(root,l,r);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
tmp[++top] = a[i].y1;
tmp[++top] = a[i].y2;
}
sort(tmp + 1,tmp + top + 1);
top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
for(int i = 1;i <= n;i++){
a[i].y1 = lower_bound(tmp + 1,tmp + top + 1,a[i].y1) - tmp;
a[i].y2 = lower_bound(tmp + 1,tmp + top + 1,a[i].y2) - tmp;
seg[++cnt] = (node){a[i].x1,a[i].y1,a[i].y2,1};
seg[++cnt] = (node){a[i].x2,a[i].y1,a[i].y2,-1};
}
sort(seg + 1,seg + cnt + 1,cmp);
for(int i = 1;i <= cnt;i++){
int l = seg[i].y1,r = seg[i].y2,k = seg[i].k;
int x = seg[i].x,x2 = seg[i + 1].x;
update(1,1,top,l,r - 1,k);
ans += 1ll * (x2 - x) * t[1].len;
}
cout << ans;
return 0;
}
这份代码能通过扫描线板子,和本题双倍经验,但是放到这题输出全 0!
有人能解释一下原因吗?