这题的代码在一般的线段树求面积并的基础上进行了修改，但是所用的思想是一样的，所以不难理解
回忆一下一般的求矩形覆盖面积，线段树节点里面有一个重要的变量，cnt。这个变量表示了该节点表示的区间被完全覆盖，如果cnt=0，说明没有被完全覆盖（但不代表没有被覆盖），要算出该节点所代表的区间被覆盖的长度，需要由它左右孩子节点被覆盖的长度相加所得。如果cnt=1，表示被完全覆盖，覆盖长度就是该区间长度。如果cnt>1说明也是被完全覆盖，不过不止覆盖了一次，在算覆盖长度的时候，和cnt=1的计算方法是一样的。注意一点，节点里还有另一个变量len，就是该区间被覆盖的长度，但是我们注意一下，这个len准确的意义应该是，被覆盖了一次或以上的长度，只是这个意义在一般的求面积问题中，不需要过分强调
而在这题中我们要计算被覆盖两次或以上的部分面积，我们在线段树节点中增设了一个变量，ss，其中s表示该该区间内被覆盖了1次或以上的长度，ss表示被覆盖了2次或以上的长度
我们是怎么计算最后的面积的？一样的道理，从下往上扫描矩形，每次添加一条矩形上下边，然后看看t[1].ss是多少，再乘上高度差。因为t[1]表示了总区间，而ss表示被覆盖两次或以上的长度，即计算时我们忽略掉只被覆盖一次的长度
问题的关键变为怎么计算一个节点的ss
分情况讨论
1.cnt>1 : 说明该区间被覆盖两次或以上，那么长度就可以直接计算，就是该区间的长度
剩下的情况就是cnt=1或cnt=0
2.先看叶子节点，因为是叶子没有孩子了，所以被覆盖两次货以上的长度就是0（无论cnt=1或cnt=0都是0，因为是叶子。。。）
3.不是叶子节点 ，且cnt=1.注意这里，cnt=1确切的意义是什么，应该是，可以确定，这个区间被完全覆盖了1次，而有没有被完全覆盖两次或以上则不知道无法确定，那么怎么怎么办了，只要加上t[lch].s + t[rch].s 即，看看左右孩子区间被覆盖了一次或以上的长度，那么叠加在双亲上就是双亲被覆盖两次或以上的长度
3.不是叶子节点，且cnt=0，确切的意义应该是不完全不知道被覆盖的情况（不知道有没有被覆盖，被覆盖了几次，长度是多少都不知道），这种情况，只能由其左右孩子的信息所得
t[lch].ss + t[rch].ss , 即直接将左右孩子给覆盖了两次或以上的长度加起来，这样才能做到不重不漏
#include <iostream> #include <cstdio> #include <algorithm> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int N = 1100; struct node1 { double l, r, h; int f; }p[N<<2]; struct node2 { int l, r; double s, ss; int cnt; }tree[N<<2]; double x[N<<2]; int cmp(node1 a,node1 b) { return a.h<b.h; } void build(int l,int r,int rt); int binary(double z,int a,int b); void update(int L,int R,int k,int l,int r,int rt); void pushup(int rt); int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); int k=0; for(int i=0;i<n;i++) { double x1, y1, x2, y2; scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); p[k].l=x1, p[k].r=x2, p[k].h=y1, p[k].f=1; p[k+1].l=x1, p[k+1].r=x2, p[k+1].h=y2, p[k+1].f=-1; x[k]=x1, x[k+1]=x2; k+=2; } sort(p,p+k,cmp); sort(x,x+k); int m=1; for(int i=1;i<k;i++) { if(x[i]!=x[i-1]) { x[m++]=x[i]; } } build(0,m-1,1); double sum=0.0; for(int i=0;i<k-1;i++) { int l=binary(p[i].l,0,m-1); int r=binary(p[i].r,0,m-1)-1; update(l,r,p[i].f,0,m-1,1); sum+=((tree[1].ss)*(p[i+1].h-p[i].h)); } printf("%.2f\n",sum); } return 0; } void build(int l,int r,int rt) { tree[rt].l=l,tree[rt].r=r,tree[rt].s=tree[rt].ss=0, tree[rt].cnt=0; if(l==r) { return ; } int mid=(l+r)/2; build(lson); build(rson); return ; } int binary(double z,int a,int b) { int l=a, r=b; while(l<=r) { int mid=(l+r)/2; if(x[mid]==z) { return mid; } else if(x[mid]<z) { l=mid+1; } else { r=mid-1; } } return -1; } void update(int L,int R,int k,int l,int r,int rt) { if(tree[rt].l==L&&tree[rt].r==R) { tree[rt].cnt+=k; pushup(rt); return ; } int mid=(l+r)/2; if(R<=mid) { update(L,R,k,lson); } else if(L>mid) { update(L,R,k,rson); } else { update(L,mid,k,lson); update(mid+1,R,k,rson); } pushup(rt); return ; } void pushup(int rt) { if(tree[rt].cnt) { tree[rt].s=x[tree[rt].r+1]-x[tree[rt].l]; } else if(tree[rt].l==tree[rt].r) { tree[rt].s=0; } else { tree[rt].s=tree[rt<<1].s+tree[rt<<1|1].s; } if(tree[rt].cnt>1) { tree[rt].ss=x[tree[rt].r+1]-x[tree[rt].l]; } else if(tree[rt].l==tree[rt].r) { tree[rt].ss=0; } else if(tree[rt].cnt==1) { tree[rt].ss=tree[rt<<1].s+tree[rt<<1|1].s; } else { tree[rt].ss=tree[rt<<1].ss+tree[rt<<1|1].ss; } return ; }
