HDU1255(覆盖的面积)

链接：https://vjudge.net/contest/260644#problem/O
思路：本来以为只用维护一个tag表示该区间被覆盖了几次就完事了，后来怎么调试都不对，经过gay一指导可能存在先把子区间全部覆盖完全，再把父区间覆盖，这样的话父区间已经被覆盖了两次但是由于tag没法表示离散的覆盖一整段所以没法实现，没办法看了题解，用len0表示区间长度，len1表示区间被覆盖一次的长度，len2表示区间被覆盖两次的长度，tag表示区间覆盖的次数，这样分类讨论一下就不会存在离散区间覆盖不了的问题。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
double seg[maxn];
int tag[maxn<<2];
double len0[maxn<<2],len1[maxn<<2],len2[maxn<<2];
int n;

struct Segment{
    double x1,y1,y2;
    int k;
    bool operator<(const Segment &r){
        return x1<r.x1||(x1==r.x1&&k>r.k);
    }
}ss[maxn];

void pushup(int o,int l,int r){
    if(tag[o]>=2){//如果覆盖两次及以上，len2等于区间长度，len1为0
        len2[o] = len0[o];
        len1[o] = 0;
    }
    else if(tag[o]==1){覆盖一次，len1等于区间长度
        len1[o] = len0[o];
        if(l==r)len2[o] = 0;//如果在端点，len2为0
        else//否则len2等于左右子树len2之和
        len2[o] =  len1[o<<1] + len1[o<<1|1] + len2[o<<1] + len2[o<<1|1];
        len1[o]-=len2[o];
    }
    else{
        if(l==r)len1[o] = len2[o] = 0;//端点全为0
        else{//否则为左右子树和
            len2[o] = len2[o<<1] + len2[o<<1|1];
            len1[o] = len1[o<<1] + len1[o<<1|1];
        }
    }
}


void build(int o,int l,int r){
  tag[o] = 0;
  len0[o] = seg[r] - seg[l-1];
  len1[o] = len2[o] = 0;
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o,l,r);
  }
}

void update(int o,int tl,int tr,int l,int r,int v){
    if(tr<l||r<tl)return;
    if(l<=tl&&tr<=r){
    tag[o]+=v;
    pushup(o,tl,tr);//一定要记住在这里pushup，把信息整合上去，因为处理的是本节点的信息。
        return;
  }
  int mid = (tl+tr)>>1;
  update(o<<1,tl,mid,l,r,v);
  update(o<<1|1,mid+1,tr,l,r,v);
  pushup(o,tl,tr);
} 

int T;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int cnt = 0;
        int tt = 0;
        for(int i=0;i<n;i++){
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            ss[cnt].x1  = a;
            ss[cnt].y1 = b;
            ss[cnt].y2 = d;
            ss[cnt++].k = 1;
            ss[cnt].x1  = c;
            ss[cnt].y1 = b;
            ss[cnt].y2 = d;
            ss[cnt++].k = -1;
            seg[tt++] = b;
            seg[tt++] = d;
        }
        sort(ss,ss+cnt);
        sort(seg,seg+tt);
        double res = 0;
        tt = unique(seg,seg+tt)-seg;
        build(1,1,tt);
        for(int i=0;i<cnt;i++){
            int l = lower_bound(seg,seg+tt,ss[i].y1)-seg+1;
            int r = lower_bound(seg,seg+tt,ss[i].y2)-seg;
            update(1,1,tt,l,r,ss[i].k);
            if(i!=cnt-1)
            res+=(ss[i+1].x1-ss[i].x1)*len2[1];//注意是后面x减当前x
        }   
        printf("%.2f\n",res);
    }
    return  0;
}