代码:
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,tl,tr,mid;
ll x1,x2,y1,y2;
ll s[MAXN],ans;
struct TREE{
ll l,r,sum,lz;
}tree[MAXN<<4];
struct XY{
ll x,y1,y2;
ll flag;
}xy[MAXN<<3];
inline void read(ll &number)
{
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') number=-number;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
number=(number<<1)+(number<<3)+(ch-'0');
ch=getchar();
}
return;
}
void pushup(ll p)
{
if(!tree[p].lz)
tree[p].sum=tree[p<<1].sum+tree[(p<<1)|1].sum;
else tree[p].sum=tree[p].r-tree[p].l;
return;
}
void build(ll l,ll r,ll p)
{
tree[p].l=s[l];
tree[p].r=s[r];
if(l-r<=1) return;
mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,(p<<1)|1);
return;
}
bool cmp(XY a,XY b)
{
return a.x<b.x;
}
void upd(ll y1,ll y2,ll p,ll flag)
{
if(tree[p].l>=y1&&tree[p].r<=y2)
{
tree[p].lz+=flag;
pushup(p);
return;
}
if(tree[p<<1].r>y1)
upd(y1,min(tree[p<<1].r,y2),p<<1,flag);
if(tree[p<<1|1].l<y2)
upd(max(tree[p<<1|1].l,y1),y2,(p<<1)|1,flag);
pushup(p);
return;
}
signed main(){
read(n);
for(ll i=1;i<=n;i++)
{
read(x1),read(y1),read(x2),read(y2);
xy[i].x=x1;
xy[i].y1=y1;
xy[i].y2=y2;
xy[i].flag=1;
xy[i+n].x=x2;
xy[i+n].y1=y1;
xy[i+n].y2=y2;
xy[i+n].flag=-1;
s[i+1]=y1;
s[i+1+n]=y2;
}
sort(s+1,s+2*n+1);
sort(xy+1,xy+2*n+1,cmp);
build(1,1,(n<<1)|1);
upd(y1,y2,1,1);
for(ll i=1;i<(n<<1);i++)
{
ans+=(xy[i].x-xy[i-1].x)*tree[i].sum;
upd(xy[i].y1,xy[i].y2,1,xy[i].flag);
}
printf("%lld\n",ans);
return 0;
}
结果:死循环