全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);
}