#include <bits/stdc++.h> using namespace std; #define maxn 100100 int c[maxn],n,m,ans,d[maxn],minn[maxn*5],sum[maxn*5],lazy[maxn*5]; struct re { int a,b; }tmp[maxn],a[maxn],b[maxn]; struct ree { int h,t,x; }p[maxn*5]; void updata(int x) { minn[x]=min(minn[x*2],minn[x*2+1]); if (minn[x*2]==minn[x*2+1]) sum[x]=(sum[x*2]+sum[x*2+1]); else if (minn[x*2]<minn[x*2+1]) sum[x]=sum[x*2]; else sum[x]=sum[x*2+1]; } #define mid (h+t)/2 void build(int x,int h,int t) { p[x].h=h; p[x].t=t; minn[x]=0; if (h==t) { p[x].x=d[h]; sum[x]=p[x].x; return; } build(x*2,h,mid); build(x*2+1,mid+1,t); p[x].x=p[x*2].x+p[x*2+1].x; updata(x); } bool cmp(re x,re y) { if (x.a<y.a||(x.a==y.a&&x.b%2>y.b%2)) return(true); else return(false); } void down(int x) { if (lazy[x]) { minn[x]+=lazy[x]; if (p[x].h!=p[x].t) { lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x]; } lazy[x]=0; } } void insert(int x,int h,int t,int sum) { down(x); if (p[x].h>t||p[x].t<h) return; if (h<=p[x].h&&p[x].t<=t) { if (sum==1) lazy[x]++; else lazy[x]--; down(x); return; } insert(x*2,h,t,sum); insert(x*2+1,h,t,sum); updata(x); } int query(int x,int h,int t) { down(x); if (p[x].h>t||p[x].t<h) return(0); if (h<=p[x].h&&p[x].t<=t) { if (minn[x]!=0)return(0);else return(sum[x]); } return(query(x*2,h,t)+query(x*2+1,h,t)); } int main() { freopen("noip.in","r",stdin); freopen("noip.out","w",stdout); cin>>n; for (int i=1;i<=n;i++) { cin>>a[i*2-1].a>>b[i*2-1].a>>a[i*2].a>>b[i*2].a; a[i*2-1].b=i*2-1; b[i*2-1].b=i*2-1; a[i*2].b=i*2; b[i*2].b=i*2; } sort(a+1,a+1+2*n,cmp); sort(b+1,b+1+2*n,cmp); int ll=0;b[0].a=99999999; for (int i=1;i<=2*n;i++) { if (b[i].a!=b[i-1].a) { d[ll]=b[i].a-b[i-1].a; ll++; } c[b[i].b]=ll; } ll--; build(1,1,ll); for (int i=1;i<=2*n;i++) { int x=(a[i].b-1)/2+1; if (a[i].b%2==0) insert(1,c[x*2-1],c[x*2]-1,-1); ans+=query(1,c[x*2-1],c[x*2]-1); if (a[i].b%2==1) insert(1,c[x*2-1],c[x*2]-1,1); } memcpy(tmp,a,sizeof(tmp)); memcpy(a,b,sizeof(b)); memcpy(b,tmp,sizeof(tmp)); ll=0;b[0].a=99999999; memset(lazy,0,sizeof(lazy)); for (int i=1;i<=2*n;i++) { if (b[i].a!=b[i-1].a) { d[ll]=b[i].a-b[i-1].a; ll++; } c[b[i].b]=ll; } ll--; build(1,1,ll); for (int i=1;i<=2*n;i++) { int x=(a[i].b-1)/2+1; if (a[i].b%2==0) insert(1,c[x*2-1],c[x*2]-1,-1); ans+=query(1,c[x*2-1],c[x*2]-1); if (a[i].b%2==1) insert(1,c[x*2-1],c[x*2]-1,1); } cout<<ans; }
链接：https://www.luogu.org/problemnew/show/P1856
题解：
和维护面积基本一致，将行列分开处理，线段树维护最小值和最小值的个数就可以了
另外注意先加边后删边（避免重复计算）