P5490扫描线求助
  • 板块学术版
  • 楼主Peter3245127684
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/7/3 22:31
  • 上次更新2023/11/6 23:42:14
查看原帖
P5490扫描线求助
223362
Peter3245127684楼主2020/7/3 22:31
#include<bits/stdc++.h>
#define int long long
#define N 400010
using namespace std;
struct node
{
	int l,r,len,siz,cov,val;
}tree[N<<2];
struct Line
{
	int x1,x2,y,val;
}line[N<<1];
int n,X1,Y1,X2,Y2,ans;
int b[N<<1];
template <typename T>
inline int read(T &x)
{
	T flg=1;x=0;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') flg=-flg;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*=flg;
}
template <typename T>
inline void write(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void writeln(T x) {write(x);puts("");}
template <typename T>
inline void writesp(T x) {write(x);putchar(' ');}
inline int cmp(Line x,Line y) {return x.y^y.y?x.y<y.y:x.val>y.val;}
inline void add(int id,int x1,int x2,int y,int val)
{
	line[id].x1=x1;line[id].x2=x2;
	line[id].y=y;line[id].val=val;
}
inline int ls(int x) {return x<<1;}
inline int rs(int x) {return x<<1|1;}
inline void updata(int i)
{
	if(!tree[i].cov) tree[i].len=tree[ls(i)].len+tree[rs(i)].len;
	else tree[i].len=tree[i].siz;
}
inline void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r) {tree[i].siz=b[l+1]-b[l];return;}
	int mid=l+r>>1;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	tree[i].siz=tree[ls(i)].siz+tree[rs(i)].siz;
}
inline void modify(int i,int l,int r,int d)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	  {
	  	tree[i].cov+=d;
	  	updata(i);
	  	return;
	  }
	int mid=tree[i].l+tree[i].r>>1;
	if(l<=mid) modify(ls(i),l,r,d);
	if(r>mid) modify(rs(i),l,r,d);
	updata(i);
}
signed main()
{
	read(n);
	for(register int i=1;i<=n;++i)
	  {
	  	read(X1);read(Y1);read(X2);read(Y2);
	  	b[(i<<1)-1]=X1;b[i<<1]=X2;
	  	add((i<<1)-1,X1,X2,Y1,1);add(i<<1,X1,X2,Y2,-1);
	  }
	n<<=1;
	sort(b+1,b+n+1);
	sort(line+1,line+n+1,cmp);
	int len=unique(b+1,b+n+1)-b-1;
	build(1,1,len);
	for(register int i=1;i<n;++i)
	  {
	  	int l=lower_bound(b+1,b+n+1,line[i].x1)-b;
	  	int r=lower_bound(b+1,b+n+1,line[i].x2)-b-1;
	  	modify(1,l,r,line[i].val);
	  	ans+=tree[1].len*(line[i+1].y-line[i].y);
	  }
	write(ans);
	return 0;
}
2020/7/3 22:31
加载中...