前两个点AC,其他8个TLE,已用线段树优化
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=1e5+10;
struct nodea{int x,ya,yb,k;}a[maxn*2];
struct nodef{int l,r,h,v;}f[maxn*8];//h=fugaishu
int n,lsy[maxn*2],sumy;LL ans;//DianXianDuanShu:(l,l):l->l+1;
bool cmp(nodea x,nodea y){return x.x<y.x;}
void pushup(int t){
f[t].v=f[t<<1].v+f[t<<1|1].v;
f[t].h=f[t<<1].h|f[t<<1|1].h?-1:0;
}
void pushdown(int t){
if(f[t].h<0) return;
f[t<<1].h=f[t<<1|1].h=f[t].h;
if(f[t].h){
f[t<<1].v=lsy[f[t<<1].r+1]-lsy[f[t<<1].l];
f[t<<1|1].v=lsy[f[t<<1|1].r+1]-lsy[f[t<<1|1].l];
}
f[t].h=-1;
return;
}
void build(int t,int l,int r){
f[t].l=l,f[t].r=r;
if(l==r) return;
int m=(l+r)/2;
build(t<<1,l,m);
build(t<<1|1,m+1,r);
return;
}
void add(int t,int ul,int ur,int v){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur&&f[t].h!=-1){
f[t].h+=v;
if(f[t].h) f[t].v=lsy[r+1]-lsy[l];
else f[t].v=0;
return;
}
pushdown(t);
int m=(l+r)/2;
if(ul<=m) add(t<<1,ul,ur,v);
if(ur>m) add(t<<1|1,ul,ur,v);
pushup(t);
return;
}
void beonly(int ul,int ur){//QuChong
int px=ul,py=ul+1;
for(;py<=ur;py++)
if(lsy[px]!=lsy[py]) lsy[++px]=lsy[py];
sumy=px-1;//besides 0
for(;px<=py;px++) lsy[px]=0;
return;
}
int efy(int x,int l,int r){//ErFen y
if(l==r) return l;
int m=(l+r)/2;
if(x<=lsy[m]) return efy(x,l,m);
return efy(x,m+1,r);
}
void ts(){
for(int i=1;i<=2*sumy;i++)
printf("%d:%d %d %d %d\n",i,f[i].l,f[i].r,f[i].h,f[i].v);
printf("\n");
}
int main(){//only beonly y
scanf("%d",&n);
for(int i=1;i<=n;i++){
int xa,ya,xb,yb;scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
a[2*i-1].x=xa;a[2*i].x=xb;
a[2*i-1].ya=a[2*i].ya=ya;a[2*i-1].yb=a[2*i].yb=yb;
a[2*i-1].k=1;a[2*i].k=-1;
lsy[2*i]=ya;lsy[2*i-1]=yb;
}
sort(lsy+1,lsy+1+2*n);beonly(1,2*n+1);
for(int i=1;i<=2*n;i++){
a[i].ya=efy(a[i].ya,1,sumy);
a[i].yb=efy(a[i].yb,1,sumy);
}
sort(a+1,a+1+2*n,cmp);build(1,1,sumy);
for(int i=1;i<=2*n;i++){
ans+=1LL*f[1].v*(a[i].x-a[i-1].x);
add(1,a[i].ya,a[i].yb-1,a[i].k);
}
printf("%lld\n",ans);
return 0;
}