零异事件
查看原帖
零异事件
999274
CNS_5t0_0r2楼主2024/7/4 15:25

这是我扫描线的代码:

#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;
}

这份代码能通过扫描线板子,和本题双倍经验,但是放到这题输出全 00!

有人能解释一下原因吗?

2024/7/4 15:25
加载中...