这一题对新手不友好，细节太多。但它很有价值。想要弄懂这一题，需要透彻地掌握线段树的本质。

个人认为难点不在于扫描线，因此本篇题解就不再论述扫描线算法，重点讨论如何用线段树维护区间覆盖问题。

错误思路分析

先将把目标抽象出来：1. 查询区间[l, r]被覆盖的长度；2. 区间修改，即区间内每个数加上一个数

我们的第一反应是令t[p].len为当前节点代表的区间被覆盖的长度。然后t[p].len=t[p1].len+t[p2].len。然后你就去愉快的写代码了，可是你会发现写到一半写不下去了。因为有区间修改操作时，你无法维护信息了。

所以马上想到增加一个域cnt表示当前节点代表的区间被覆盖的次数。更新只需t[p].cnt=min(t[p1].cnt, t[p2].cnt)。很好，你又开始愉快的写代码了，可是你发现当写到这里时：

void upd(int p,int l,int r,int add) {
    if(t[p].l>=l && t[p].r<=r) {
        t[p].cnt+=add,t[p].add+=add;
        if(t[p].cnt>0) t[p].len=raw(t[p].r+1)-raw(t[p].l);
        else t[p].len=t[p1].len+t[p2].len;
        return;
    }
    ... ...
}

如果t[p].cnt减到0的时候，出问题了。因为你想啊，t[p].cnt减了1变为了0，那这时p1和p2的cnt也要减1。如果p1的cnt变为0了。它的len就发生变化了。可是你直接写t[p].len=t[p1].len+t[p2].len，用到的t[p1].len是没更新过的len。

换句话说，你执行到这里时，是从上到下的顺序。可是你却用到了下面的信息。这显然就会出错。

发现了错误，我们可以这样改：因为用到t[p1].len和t[p2].len必须是最新值，那么我就先pushDown算出t[p1].len和t[p2].len的值不就行了吗？可是同理，算t[p1].len时，需要用到t[p1的儿子].len的最新值，因此你又要再pushDown算出t[p1的儿子].len的值… …你可以发现，如果一个t[p].cnt减到0了，那么需要递归到最底层才能完成更新。TLE没得跑了。

所以，按照这种方法写，可以写，可是就退化成暴力了。

解法一：利用特殊性质

强调下此时t[p].cnt表达的含义：当前区间被覆盖的次数，跟其它节点无关。

可以发现，因为对于修改区间[l, r]操作，是一对一对的。

所以，一个节点代表的区间被覆盖的次数不需要继承其父亲信息的情况。

因此需要去掉pushDown。

那么当出现t[p].cnt减为0时，你写t[p].len=t[p1].len+t[p2].len就是对的。因为t[p].cnt减到0跟t[p1].cnt又没有关系，此时t[p1].len是最新值。

然后你就可以愉快的写代码了。其实就是错误思路去掉pushDown即可。

解法二：就要用pushDown！

其实不管用不用，只要能保证正确性并且时间复杂度合理就行。

回顾错误思路，虽然用了pushDown，可是正确性错误。

那么就要想出一种方法既能用pushDown、也能保证正确性、时间也OK。

你可以令t[p].len表示当前区间表示的长度，t[p].mini表示当前区间内的最小值，t[p].minlen表示最小值的长度。

t[p].len建树时就预处理出来。维护区间最小值pushDown维护即可。那如何维护最小值长度呢？

在pushUp中这么写：（很简单的逻辑，不再解释

void pushUp(int p) {
    t[p].mini=min(t[p1].mini,t[p2].mini);
    double minlen=0;
    if(t[p].mini==t[p1].mini) minlen+=t[p1].minlen;
    if(t[p].mini==t[p2].mini) minlen+=t[p2].minlen;
    t[p].minlen=minlen;
}

维护搞定了，查询时，如果区间最小值为0，输出(区间代表长度-区间最小值长度)。否则直接输出区间长度即可。

你会发现在upd函数的从上到下过程中，不会出现更新当前结点信息需要用到下面信息的情况。因此正确性得以保证。

总结

不要拘泥于线段树的模板。看见区间修改就一定要pushDown这种思想不利于今后的学习。

总的来说，不管用不用pushDown，只要保证正确性无误、时间OK即可。线段树不是算法，是一种数据结构，它只是一个工具。如何利用工具，才是关键。

如果有疑惑/错误还请指出，交流愉快～

利用特殊性质：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define p1 (p<<1)
#define p2 (p<<1|1)

const int N=10005;

struct T {
    int l,r,cnt;
    double len;
} t[N*16];
struct A {
    double x,y1,y2;
    int add;
} a[N*2];
int n,len;
double lsh[N*2];

bool cmp(A u,A v) {return u.x<v.x;}
int val(double x) {return lower_bound(lsh+1,lsh+1+len,x)-lsh;}
double raw(int x) {return lsh[x];}

void pushUp(int p) {t[p].len=(t[p].cnt>0)?raw(t[p].r+1)-raw(t[p].l):t[p1].len+t[p2].len;}
void build(int p,int l,int r) {
    t[p]={l,r,0,0};
    if(l==r) return;
    int mid=l+r>>1;
    build(p1,l,mid),build(p2,mid+1,r);
}

void upd(int p,int l,int r,int add) {
    if(t[p].l>=l && t[p].r<=r) {t[p].cnt+=add,pushUp(p); return;}
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) upd(p1,l,r,add);
    if(r>mid) upd(p2,l,r,add);
    pushUp(p);
}

int main()
{
    for(int tim=1;;tim++) {
        scanf("%d",&n);
        if(!n) break;
        printf("Test case #%d\n",tim);
        for(int i=1;i<=n;i++) {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[i]={x1,y1,y2,1},a[i+n]={x2,y1,y2,-1};
            lsh[i]=y1,lsh[i+n]=y2;
        }
        n*=2;
        sort(a+1,a+1+n,cmp),sort(lsh+1,lsh+1+n);
        len=unique(lsh+1,lsh+1+n)-lsh-1;
        build(1,1,len-1);
        double ans=0;
        upd(1,val(a[1].y1),val(a[1].y2)-1,a[1].add);
        for(int i=2;i<=n;i++) {
            ans+=t[1].len*(a[i].x-a[i-1].x);
            upd(1,val(a[i].y1),val(a[i].y2)-1,a[i].add);
        }
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}

使用pushDown

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define p1 (p<<1)
#define p2 (p<<1|1)

const int N=10005;

struct T {
    int l,r,mini,add;
    double len; //区间长度
    double minlen; //区间最小值的区间长度
} t[N*8];
struct A {
    double x,y1,y2;
    int add;
} a[N*2];
int n,len;
double lsh[N*2];

bool cmp(A u,A v) {return u.x<v.x;}
int val(double x) {return lower_bound(lsh+1,lsh+1+len,x)-lsh;}
double raw(int x) {return lsh[x];}

void pushUp(int p) {
    t[p].mini=min(t[p1].mini,t[p2].mini);
    double minlen=0;
    if(t[p].mini==t[p1].mini) minlen+=t[p1].minlen;
    if(t[p].mini==t[p2].mini) minlen+=t[p2].minlen;
    t[p].minlen=minlen;
}

void build(int p,int l,int r) {
    double len=raw(r+1)-raw(l);
    t[p]={l,r,0,0,len,len};
    if(l==r) return;
    int mid=l+r>>1;
    build(p1,l,mid),build(p2,mid+1,r);
}

void pushDown(int p) {
    t[p1].add+=t[p].add,t[p2].add+=t[p].add;
    t[p1].mini+=t[p].add,t[p2].mini+=t[p].add;
    t[p].add=0;
}

void upd(int p,int l,int r,int add) {
    if(t[p].l>=l && t[p].r<=r) {t[p].mini+=add,t[p].add+=add; return;}
    if(t[p].add!=0) pushDown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) upd(p1,l,r,add);
    if(r>mid) upd(p2,l,r,add);
    pushUp(p);
}

int main()
{
    for(int tim=1;;tim++) {
        scanf("%d",&n);
        if(!n) break;
        printf("Test case #%d\n",tim);
        for(int i=1;i<=n;i++) {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[i]={x1,y1,y2,1},a[i+n]={x2,y1,y2,-1};
            lsh[i]=y1,lsh[i+n]=y2;
        }
        n*=2;
        sort(a+1,a+1+n,cmp),sort(lsh+1,lsh+1+n);
        len=unique(lsh+1,lsh+1+n)-lsh-1;
        build(1,1,len-1);
        double ans=0;
        upd(1,val(a[1].y1),val(a[1].y2)-1,a[1].add);
        for(int i=2;i<=n;i++) {
            double len=t[1].len;
            if(!t[1].mini) len-=t[1].minlen;
            ans+=len*(a[i].x-a[i-1].x);
            upd(1,val(a[i].y1),val(a[i].y2)-1,a[i].add);
        }
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}