题意：
求n个矩阵面积交
分析：
其实和求矩阵面积并是一样的思想
我们只需增加一个nsum数组储存区间中覆盖2次及以上的长度就行
#include <bits/stdc++.h> #define maxn 200002 #define tmp (st<<1) #define mid ((l+r)>>1) #define lson l,mid,tmp #define rson mid+1,r,tmp|1 using namespace std; int cnt[maxn<<2]; double sum[maxn<<2]; double nsum[maxn<<2]; double x[maxn]; struct Seg{ double h,l,r; int s; Seg(){} Seg(double a,double b,double c,int d):l(a),r(b),h(c),s(d){} bool operator<(const Seg &cmp)const{ return h<cmp.h; } }ss[maxn]; void push_up(int st,int l,int r){ if(cnt[st]==1){ sum[st]=x[r+1]-x[l]; nsum[st]=sum[tmp]+sum[tmp|1]; } else if(cnt[st]>=2)sum[st]=nsum[st]=x[r+1]-x[l]; else if(l==r)nsum[st]=sum[st]=0; else { sum[st]=sum[tmp]+sum[tmp|1]; nsum[st]=nsum[tmp]+nsum[tmp|1]; } } void update(int L,int R,int c,int l,int r,int st){ if(L<=l&&r<=R){ cnt[st]+=c; push_up(st,l,r); return ; } if(L<=mid)update(L,R,c,lson); if(R>mid)update(L,R,c,rson); push_up(st,l,r); } int main(){ int n,m,loop; scanf("%d",&loop); while(loop--){ scanf("%d",&n); double a,b,c,d,ans=0; m=0; while(n--){ scanf("%lf%lf%lf%lf",&a,&b,&c,&d); x[m]=a; ss[m++]=Seg(a,c,b,1); x[m]=c; ss[m++]=Seg(a,c,d,-1); } sort(x,x+m); sort(ss,ss+m); for(int i=0;i<m;++i){ int l=lower_bound(x,x+m,ss[i].l)-x; int r=lower_bound(x,x+m,ss[i].r)-x-1; update(l,r,ss[i].s,0,m-1,1); ans+=nsum[1]*(ss[i+1].h-ss[i].h); } printf("%.2lf\n",ans); } return 0; }