社区讨论
线段树,求条,玄关
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 条回复,欢迎继续交流。
正在加载回复...