社区讨论

18pts AC on #1~#2 TLE on #3~#10求条(麻风良好)

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mhj3l3cj
此快照首次捕获于
2025/11/03 20:09
4 个月前
此快照最后确认于
2025/11/03 20:09
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
#define ls id<<1
#define rs id<<1|1 
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<48){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}

const int N=1e5+5;
int n,xx[2*N],yy[2*N],zhenx[2*N],zheny[2*N];
struct sw{
	int x_1,y_1,x_2,y_2;
}a[2*N];
struct WS{
	int l,r,op;
};
vector<WS> g[2*N];
struct note{
	int l,r,tag,mx;
}tr[16*N];

inline void ADD(int id,int k){
	tr[id].mx+=k;tr[id].tag+=k;
}

inline void pushdown(int id){
	//printf("id=%lld\n",id);
	ADD(ls,tr[id].tag);ADD(rs,tr[id].tag);
	//printf("%lld += %lld\n",ls,tr[id].tag);
	//printf("%lld += %lld\n",rs,tr[id].tag);
	tr[id].tag=0;
} 

inline void build(int id,int l,int r){
	//printf("(%lld,%lld,%lld)\n",id,l,r);
	//printf("[%lld,%lld]\n",l,r+1);
	tr[id].l=l,tr[id].r=r,tr[id].tag=tr[id].mx=0;
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}

inline void update(int id,int l,int r,int k){
	//printf("update[%lld,%lld],k=%lld\n",l,r+1,k);
	if(l<=tr[id].l&&tr[id].r<=r){
		//printf("[%lld,%lld] included\n",tr[id].l,tr[id].r+1);
		ADD(id,k);
		//printf("[%lld,%lld].mx:%lld\n",tr[id].l,tr[id].r+1,tr[id].mx);
		return ;
	}
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1;
	if(l<=mid){
		//printf("go ls %lld\n",ls);
		update(ls,l,r,k);
	} 
	if(r>mid){
		//printf("go rs %lld\n",rs);
		update(rs,l,r,k);	
	} 
	tr[id].mx=max(tr[ls].mx,tr[rs].mx);
}

inline int query(int id,int l,int r){
	if(!tr[id].l||!tr[id].r){
		return 0;
	}
	//printf("id=%lld l=%lld r=%lld [%lld,%lld]\n",id,tr[id].l,tr[id].r,tr[id].l,tr[id].r+1);
	if(tr[id].mx==0){
		//printf("id=%lld (%lld,%lld) [%lld,%lld]\n",id,tr[id].l,tr[id].r,tr[id].l,tr[id].r+1);
		//printf("[%lld,%lld] is empty\n",zhenx[tr[id].l],zhenx[tr[id].r+1]);
		return zhenx[tr[id].r+1]-zhenx[tr[id].l];
	} 
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1,ans=0;
	if(l<=mid) ans+=query(ls,l,r);
	if(r>mid) ans+=query(rs,l,r); 
	return ans;
}

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i].x_1=read(),a[i].y_1=read(),a[i].x_2=read(),a[i].y_2=read();
		xx[2*i-1]=a[i].x_1,xx[2*i]=a[i].x_2;yy[2*i-1]=a[i].y_1,yy[2*i]=a[i].y_2;
	}
	/*
	for(int i=1;i<=2*n;i++){
		printf("%lld ",xx[i]);
	}
	printf("\n");
	for(int i=1;i<=2*n;i++){
		printf("%lld ",yy[i]);
	}
	printf("\n");
	*/
	//cout<<"111"<<endl;
	sort(xx+1,xx+2*n+1);sort(yy+1,yy+2*n+1);
	int lenx=unique(xx+1,xx+2*n+1)-xx-1;
	int leny=unique(yy+1,yy+2*n+1)-yy-1;
	//cout<<"222"<<endl;
	for(int i=1;i<=n;i++){
		//cout<<"i="<<i<<endl;
		int posx1=lower_bound(xx+1,xx+lenx+1,a[i].x_1)-xx;
		int posx2=lower_bound(xx+1,xx+lenx+1,a[i].x_2)-xx;
		int posy1=lower_bound(yy+1,yy+leny+1,a[i].y_1)-yy;
		int posy2=lower_bound(yy+1,yy+leny+1,a[i].y_2)-yy;
		//printf("(%lld,%lld)+(%lld,%lld)\n",posx1,posy1,posx2,posy2);
		zhenx[posx1]=a[i].x_1;zhenx[posx2]=a[i].x_2;
		zheny[posy1]=a[i].y_1;zheny[posy2]=a[i].y_2;
		a[i].x_1=posx1,a[i].x_2=posx2,a[i].y_1=posy1,a[i].y_2=posy2;
		g[posy1].push_back((WS){posx1,posx2,1});
		g[posy2].push_back((WS){posx1,posx2,-1});
	}
	build(1,1,2*n-1);
	/*
	for(int i=1;i<=2*n;i++){
		printf("%lld ",zhenx[i]);
	}
	printf("\n");
	for(int i=1;i<=2*n;i++){
		printf("%lld ",zheny[i]);
	}
	printf("\n");
	*/
	int ans=0;
	for(int i=1;i<2*n;i++){
		for(int j=0;j<g[i].size();j++){
			//printf("add (%lld,%lld,%lld)\n",g[i][j].l,g[i][j].r-1,g[i][j].op);
			update(1,g[i][j].l,g[i][j].r-1,g[i][j].op);
			int que=query(1,1,2*n-1);
			//printf("(%lld-%lld)*(%lld-%lld-%lld)\n",zheny[i+1],zheny[i],zhenx[2*n],zhenx[1],que);
			ans=ans+(zheny[i+1]-zheny[i])*(zhenx[2*n]-zhenx[1]-que);
		}
	}
	printf("%lld",ans);
	return 0;
} 
rt,dalao求条QaQ,尽力了
另外就是,我也不知道为什么,我N=1e5+5会RE,N=2e5+5会TLE

回复

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

正在加载回复...