社区讨论

线段树,求条,玄关

P1856[IOI 1998 / USACO5.5] 矩形周长 Picture参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mm76x4v2
此快照首次捕获于
2026/03/01 11:28
7 天前
此快照最后确认于
2026/03/03 20:00
4 天前
查看原帖
代码先写了从左往右扫的一半,样例输出9494,在面积AC代码基础上修改,求条,玄关
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll ans=0;
ll y[210000];
struct smx{
	ll y_1,y_2,x,mark;
}line[210000];
struct node{
	ll c,tag;
}tr[810000];
bool cmp(smx a,smx b){
	return a.x<b.x;
}
void pushup(ll rt,ll l,ll r){
	if(!tr[rt].tag){
		if(l==r)tr[rt].c=0;
		else tr[rt].c=tr[rt<<1].c+tr[rt<<1|1].c;
	}
}
void change(ll rt,ll l,ll r,ll _y1,ll _y2,ll k){
	if(l>=_y1&&r<=_y2){
		tr[rt].tag+=k;
		if(tr[rt].tag)tr[rt].c=y[r+1]-y[l];
		else tr[rt].c=0;
		pushup(rt,l,r);
		return;
	}
	long long mid=l+r>>1;
	if(_y1<=mid)change(rt<<1,l,mid,_y1,_y2,k);
	if(mid<_y2)change(rt<<1|1,mid+1,r,_y1,_y2,k);
	pushup(rt,l,r);
}
int main(){
	ll _y1,_y2;
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		ll sx,sy,ex,ey;
		scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
		y[(i<<1)-1]=sy;
		y[i<<1]=ey;
		line[(i<<1)-1]={sy,ey,sx,3};
		line[i<<1]={sy,ey,ex,-3};
	}
	n<<=1;	
	int h=0;
	stable_sort(y+1,y+n+1);
	stable_sort(line+1,line+n+1,cmp);
	ll len=unique(y+1,y+n+1)-y;
	for(ll	i=1;i<n;++i){
		_y1=lower_bound(y+1,y+len,line[i].y_1)-y;
		_y2=lower_bound(y+1,y+len,line[i].y_2)-y-1;
		change(1,1,len,_y1,_y2,line[i].mark);
		ans+=abs(tr[1].c-h);
		h=tr[1].c;
	}
	cout<<ans;
	printf("%lld\n",ans);
	return 0;
}

回复

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

正在加载回复...