社区讨论

为什么开八倍空间过不了开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 条回复,欢迎继续交流。

正在加载回复...