我裂开了
查看原帖
我裂开了
335094
Lucifero楼主2021/2/25 15:34

全WA求助,调了一中午

#include <bits/stdc++.h>
#define ls (p<<1)
#define rs ((p<<1)+1)
using namespace std;
class SegmentTree
{
public:
	int v,l,r;
	int lazy,c;
	bool lc,rc;
}tree[400001];
class ScanMachine
{
public:
	int l,r,w,g;
}line[400001];
bool operator<(ScanMachine l,ScanMachine r){ return l.w<r.w; }
int tx[50001],n,ans;
void pushup(int p)
{
	if (tree[p].lazy!=0)
	{
		tree[p].c=1;
		tree[p].lc=tree[p].rc=true;
		tree[p].v=tree[p].r-tree[p].l;
		return;
	}
	tree[p].lc=tree[ls].lc;
	tree[p].rc=tree[rs].rc;
	tree[p].v=tree[ls].v+tree[rs].v;
	tree[p].c=tree[ls].c+tree[rs].c;
	if (tree[ls].rc && tree[rs].lc) tree[p].c--;
}
void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r;
	if (l+1==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid,r);
}
void modify(int p,int l,int r,int d)
{
	int ll=tree[p].l,rr=tree[p].r;
	if (tx[ll]>=r || tx[rr+1]<=l)
		return;
	if (tx[ll]>=l && tx[rr+1]<=r)
	{
		tree[p].lazy+=d;
		pushup(p);
		return;
	}
	modify(ls,l,r,d);
	modify(rs,l,r,d);
	pushup(p);
}
int main()
{
	//¡¾USACO5.5.1¡¿Picture¾ØÐÎÖܳ¤
	int x1,y1,x2,y2,l,i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x1,&y1);
		scanf("%lld%lld",&x2,&y2);
		tx[i*2-1]=x1,tx[i*2]=x2;
		line[i*2-1]=(ScanMachine){x1,x2,y1,1};
		line[i*2]=(ScanMachine){x1,x2,y2,-1};
	}
	n<<=1;
	sort(line+1,line+n+1);
	sort(tx+1,tx+n+1);
	l=unique(tx+1,tx+n+1)-tx-1;
	build(1,1,l);
	for(i=1;i<n;i++)
	{
		modify(1,line[i].l,line[i].r,line[i].g);
		ans+=(line[i+1].w-line[i].w)*tree[1].v*2;
	}
	printf("%lld",ans);
}
2021/2/25 15:34
加载中...