社区讨论
为什么开八倍空间过不了开16倍AC
P5490【模板】扫描线 & 矩形面积并参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mjph7fxu
- 此快照首次捕获于
- 2025/12/28 16:37 2 个月前
- 此快照最后确认于
- 2025/12/31 23:55 2 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
long long n;
long long tomb[1600010],cfind[1600010];
long long ans;
map<int,int> q;
struct ed
{
long long b,c;
long long nowx;
long long sum;
}a[1600010];
struct ev
{
long long cnt;
long long len;
long long l,r;
long long start;
long long fa;
}tree[1600010];
bool cmp1(ed x,ed y)
{
if(x.nowx==y.nowx) return x.b<y.b;
return x.nowx<y.nowx;
}
long long tom=0;
void pushup(int p)
{
if(tree[p].cnt) tree[p].len=cfind[tree[p].r+1]-cfind[tree[p].l];
else
tree[p].len=tree[p*2].len+tree[p*2+1].len;
}
void build(int p,int ll,int rr,int last)
{
tree[p].fa=last;
if(rr==ll)
{
tree[p].l=ll;
tree[p].r=rr;
return ;
}
int mid=(ll+rr)/2;
build(p*2,ll,mid,p);
build(p*2+1,mid+1,rr,p);//mid
tree[p].l=ll;
tree[p].r=rr;
}
void add(int p,int x,int y,int cntk)
{
if(x>y) return ;
if(x<=tree[p].l&&y>=tree[p].r)
{
tree[p].cnt+=cntk;
pushup(p);
return ;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid) add(p*2,x,y,cntk);
if(y>mid) add(p*2+1,x,y,cntk);
pushup(p);
// cout<<p<<" "<<tree[p].len<<endl;
}
int main()
{
cin>>n;
long long tot=0;
for(int i=1;i<=n;i++)
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
tomb[++tot]=y1;
a[tot].b=y1;
a[tot].c=y2;
a[tot].sum=1;
a[tot].nowx=x1;
tomb[++tot]=y2;
a[tot].b=y1;
a[tot].c=y2;
a[tot].sum=-1;
a[tot].nowx=x2;
}
sort(tomb+1,tomb+tot+1);
tomb[0]=-1;
for(int i=1;i<=tot;i++)
{
if(tomb[i]!=tomb[i-1]) q[tomb[i]]=++tom;
cfind[tom]=tomb[i];
}
sort(a+1,a+tot+1,cmp1);
for(int j=1;j<=tot;j++)
{a[j].b=q[a[j].b];a[j].c=q[a[j].c];}
build(1,1,tom-1,1);//tom-1
for(int i=1;i<=tot;i++)
{
if(i!=1)
ans+=1ll*tree[1].len*(a[i].nowx-a[i-1].nowx);
add(1,a[i].b,a[i].c-1,a[i].sum);
}
cout<<ans;
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...