讲这题之前,我先介绍下线段树扫描线,可能昨晚睡眠不足,导致今天连递归都没看懂,服了.
扫描线只是利用线段树思路解决问题的一种方式而已.
就拿本题来说要你计算图形面积.
图片说明
这是题目的样例,讲下重点和我对这题的理解，虽然不是很透彻..首先我们可以把x轴按x的值切分，我们要用y轴值进行快速更新.首先这个更新可以用线段树，存tr数组的话考虑4个变量l，r表示当前节点的左右区间，然后用cnt和len分别表示这个矩形在这个区域叠加了几次以及这个区域所占长度，显然因为y是浮点数，不适合我们直接建树，我们需要离散化一下.我们拿build把节点建树，然后我们modify进行更新，更新时候有个pushup操作.等会单独讲，modify就是进行区间更新，和普通的线段树没什么两样，但是这个是区间更新，但是这个是扫描线，有什么特殊的地方呢？就是他增加和减少都是对称的，并且一段＞0那么这段长度就是这个区间大小.我们可以直接更新区间即可，因为小的不影响大的正确性。这就是为什么不要lazy标记的原因.而pushup我们怎么更新呢？首先对于cnt＞0的那么一定是区间长度.对于＝0就有两个，一个是只有一个节点，那么显然是0，不然就是左右儿子的和了.为什么是这个呢？（指左右儿子）因为一旦这个区间里面更新了值，那么它的信息一定会返回到比它大的区间.好了，这题就结束了，我之前不知道为啥被pushup思路卡了，呜呜呜(┯_┯).
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct edge{
    double x,y1,y2;
    int k;
    bool operator <(const edge &t)const
    {
        return x<t.x;    
    }
}op[N*2];

struct node{
    int l,r,cnt;
    double len;
}tr[N*8];

vector<double>v;


void pushup(int u)
{
    if(tr[u].cnt)
    {
        tr[u].len=v[tr[u].r+1]-v[tr[u].l];
    }
    else if(tr[u].l!=tr[u].r)
    {
        tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    }
    else
    {
        tr[u].len=0;
    }
}

void modify(int u,int l,int r,int k)
{
    if(l<=tr[u].l&&r>=tr[u].r)
    {
        tr[u].cnt+=k;
        pushup(u);
        return;
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)    modify(u<<1,l,r,k);
        if(r>mid)     modify(u<<1|1,l,r,k);
        pushup(u);
    }
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]={l,r,0,0};
        return;
    }
    else
    {
        int mid=l+r>>1;
        tr[u]={l,r,0,0};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}

int find(double x)//寻找x的位子
{
    return lower_bound(v.begin(),v.end(),x)-v.begin();
}

int main()
{
    int n,T=1;
    while(cin>>n,n)
    {   
        v.clear();
        for(int i=0,j=0;i<n;i++)
        {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            op[j++]={x1,y1,y2,1};
            op[j++]={x2,y1,y2,-1};
            v.push_back(y1);v.push_back(y2);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        build(1,0,v.size()-2);
        sort(op,op+2*n);
        double ans=0.0;
        for(int i=0;i<2*n;i++)
        {
            if(i>0) ans+=tr[1].len*(op[i].x-op[i-1].x);
            modify(1,find(op[i].y1),find(op[i].y2)-1,op[i].k);
        }
        printf("Test case #%d\n",T++);
        printf("Total explored area: %.2lf\n",ans);
        puts("");
    }
    return 0;
}