18pts,剩下全 WA
查看原帖
18pts,剩下全 WA
926886
kind_Ygg楼主2024/10/10 09:51
#include<bits/stdc++.h>
#define int long long 
#define y1 puck
int ls(int x){return x*2;}
int rs(int x){return x*2+1;}
using namespace std;
const int N=6e5+5;
int n;
int x1,y1,x2,y2;
int ans=0;
struct Line{
	int x;
	int l,r;
	int val;
}line[N];
int s[N];
int tree[N];
int tot;
int tag[N];
int f[N];
bool cmp(int a,int b){return a<b;}
bool cmp1(Line a,Line b){return a.x<b.x;}
void push_up(int p,int l,int r)
{
	if(tag[p]>0) tree[p]=f[r]-f[l-1];
	else tree[p]=tree[ls(p)]+tree[rs(p)];
}
void update(int l,int r,int k,int s,int t,int p)
{
	if(l<=s and t<=r)
	{
		tag[p]+=k;
		push_up(p,s,t);
		return;
	}
	int mid=s+((t-s)>>1);
	if(l<=mid) update(l,r,k,s,mid,ls(p));
	if(mid+1<=r) update(l,r,k,mid+1,t,rs(p));
	push_up(p,s,t);
}
signed main()
{
	freopen("P5490_3.in","r",stdin);
	freopen("P5490.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		line[++tot]=(Line){x1,y1,y2,1};
		s[tot]=y1;
		line[++tot]=(Line){x2,y1,y2,-1};
		s[tot]=y2;
	}
	sort(s+1,s+tot+1,cmp);
	sort(line+1,line+tot+1,cmp1);
	int len1=unique(s+1,s+tot+1)-s-1;
	for(int i=1;i<len1;i++)
		f[i]=s[i+1]-s[i],f[i]=f[i-1]+f[i];
	for(int i=1;i<=tot;i++)
	{
		int L=lower_bound(s+1,s+len1+1,line[i].l)-s;
		int R=lower_bound(s+1,s+len1+1,line[i].r)-s-1;
//		cout<<L<<' '<<R<<'\n';
		update(L,R,line[i].val,1,len1-1,1);
		if(i!=tot)
			ans+=tree[1]*(line[i+1].x-line[i].x);
//		cout<<tree[1]<<' ';
//		for(int i=1;i<=(len1-1)*4;i++)
//			cout<<tree[i]<<'|'<<tag[i]<<' ';
//		cout<<'\n';
	}
	cout<<ans<<'\n';
	return 0;
}
2024/10/10 09:51
加载中...