做了3天不知道哪里错了,还是0分~
查看原帖
做了3天不知道哪里错了,还是0分~
42760
⊱⋛赫宇⋚⊰楼主2021/8/29 10:23
#include<bits/stdc++.h>
#define LL long long
#define I inline
#define RI register int 
#define maxn 200010
using namespace std;
I int read()
{
	RI res=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch&15);ch=getchar();}
	return res*f;
} 
int n,rel[maxn<<1];LL ans;
struct Scanline{
	int x,y1,y2,val;
	friend I bool operator <(const Scanline &x, const Scanline &y){
		if(x.x==y.x)return x.val>y.val;
		return x.x<y.x;
	}
}line[maxn<<1];
struct Tree{
	int l,r,cnt,len;
	#define ls(x) x<<1
	#define rs(x) x<<1|1
}tree[maxn<<2];
int M;
I void build(int l,int r,int id)
{
	tree[id].l=l;tree[id].r=r;
//	cout<<id<<" ";
	if(l==r)return;
	int mid=l+r>>1;
	build(l,mid,ls(id));build(mid+1,r,rs(id));
	return ;
}
int Y[maxn<<1];
I void up(int id)
{
	if(tree[id].l==M&&tree[id].r==M)return;
	if(tree[id].cnt)tree[id].len=Y[tree[id].r+1]-Y[tree[id].l];
	else tree[id].len= tree[id].l==tree[id].r ? 0:tree[ls(id)].len+tree[rs(id)].len;
	return;

}
I void Que(int l,int r,int id,int k)
{

	if(tree[id].l>=l&&tree[id].r<=r){
		tree[id].cnt+=k;
		up(id);
		return;
	}
	if(tree[ls(id)].r>=l)Que(l,r,ls(id),k);
	if(tree[rs(id)].l<=r)Que(l,r,rs(id),k);
	up(id);
}
int main()
{
	n=read();
	for(RI i=1;i<=n;i++)
	{
		line[(i<<1)-1].x=read();
		Y[(i<<1)-1]=line[(i<<1)-1].y1=line[i<<1].y1=read();
		
		line[(i<<1)].x=read();
		Y[i<<1]=line[(i<<1)-1].y2=line[i<<1].y2=read();
		
		line[(i<<1)-1].val=1;
		line[i<<1].val=-1;
		
	}
	n<<=1;
	sort(Y+1,Y+1+n);
	sort(line+1,line+1+n);
	int tot=unique(Y+1,Y+1+n)-Y-1;
	for(RI i=1;i<=n;i++)
	{
	   int k1=lower_bound(Y+1,Y+1+tot,line[i].y1)-Y;
	   int k2=lower_bound(Y+1,Y+1+tot,line[i].y2)-Y;
	   rel[k1]=line[i].y1;
	   rel[k2]=line[i].y2;	M = max(M, k2);
	   line[i].y1=k1;
	   line[i].y2=k2;
	}
	build(1,n,1);
	for(RI i=1;i<n;i++)
	{
		Que(line[i].y1,line[i].y2-1,1,line[i].val);
//		cout<<tree[1].len<<" "<<(line[i+1].x-line[i].x)<<endl;
		ans+=tree[1].len*(line[i+1].x-line[i].x);
	}
	printf("%lld\n",ans);
	return 0;
}
2021/8/29 10:23
加载中...