社区讨论

蒟蒻本地都过不了,求条

P5490【模板】扫描线 & 矩形面积并参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi8gacwa
此快照首次捕获于
2025/11/21 13:59
3 个月前
此快照最后确认于
2025/11/21 16:13
3 个月前
查看原帖
看不出哪里有问题
CPP
#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
#define mid l+r>>1
using namespace std;
const int maxn=3e5+10;
struct node{
	int lx,ly,rx,ry;
}rec[maxn];
struct node1{
	int x,y,y2,w;
}line[maxn];
bool cmp(node1 x,node1 y){
	return x.x<y.x;
}
int ysort[maxn],len[maxn<<2],cover[maxn<<2],times[maxn<<2];
int prepare(int n){
	sort(ysort+1,ysort+n+1);
	int m=1;
	for(int i=2;i<=n;i++){
		if(ysort[m]!=ysort[i])ysort[++m]=ysort[i];
	}
	ysort[m+1]=ysort[m];
	return m;
}
int rank(int n,int num){
	int ans=0;
	int l=1,r=n;
	while(l<=r){
		if(ysort[mid]>=num){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	return ans;
}
void build(int l,int r,int i){
	if(l<r){
		build(l,mid,ls);
		build(mid+1,r,rs);
	}
	len[i]=ysort[r+1]-ysort[l];
	times[i]=0;
	cover[i]=0;
}
void up(int i){
	if(times[i]>0){
		cover[i]=len[i];
	}else{
		cover[i]=cover[ls]+cover[rs];
	}
}
void add(int jobl,int jobr,int jobv,int l,int r,int i){
	if(jobl<=l&&r<=jobr){
		times[i]+=jobv;
	}else{
		if(jobl<=mid){
			add(jobl,jobr,jobv,l,mid,ls);
		}
		if(jobr>mid){
			add(jobl,jobr,jobv,mid+1,r,rs);
		}
	}
	up(i);
}
long long compute(int n){
	for(int i=1,j=n+1;i<=n;i++,j++){
		ysort[i]=rec[i].ly;
		ysort[j]=rec[i].ry;
		line[i].x=rec[i].lx;
		line[i].y=rec[i].ly;
		line[i].y2=rec[i].ry;
		line[i].w=1;
		line[j].x=rec[i].rx;
		line[j].y=rec[i].ly;
		line[j].y2=rec[i].ry;
		line[j].w=-1;
	}
	n<<=1;
	int m=prepare(n);
	build(1,m,1);
	sort(line+1,line+n+1,cmp);
	long long ans=0;
	for(int i=1,pre=0;i<=n;i++){
		ans+=(long long)cover[1]*(line[i].x-pre);
		pre=line[i].x;
		add(rank(m,line[i].y),rank(m,line[i].y2)-1,line[i].w,1,m,1);
	}
	return ans;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>rec[i].lx>>rec[i].ly>>rec[i].rx>>rec[i].ry;
	}
	cout<<compute(n);
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...