莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 对 y 轴数据进行离散化，将区间[y1, y2]看成一个点，然后对其做线段树
2. 对 x 轴进行排序，all (x[i] - x[i-1]) * y 就是 answer
3. find 函数：返回第一个大于等于 y 的位置
4. pushup 函数：维护区间长度，主要是根节点的
5. build 函数：建立线段树，不需要 pushup
6. modify 函数：修改区间覆盖次数，并且需要 pushup

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
struct Segment
{
    double x,y1,y2;
    int k;
    bool operator< (const Segment &t) const
    {
        return x<t.x;
    }
}seg[N*2];
struct Node
{
    int l,r;
    int cnt; //该区间覆盖次数
    double len; //该区间长度
}tr[N*8];
vector<double> ys;

//找到大于等于y的第一个位置
int find(double y)
{
    return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}

void pushup(int u)
{
    //覆盖次数不为零
    if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[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 build(int u,int l,int r)
{
    tr[u]={l,r,0,0};
    if(l!=r)
    {
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}

void modify(int u,int l,int r,int k)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].cnt+=k;
        pushup(u);
    }
    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);
    }
}

int main()
{
    int T=1;
    while(cin>>n,n)
    {
        //多组数据初始化
        ys.clear();

        for(int i=0,j=0;i<n;i++)
        {
            double x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            seg[j++]={x1,y1,y2,1};
            seg[j++]={x2,y1,y2,-1};
            ys.push_back(y1);
            ys.push_back(y2);
        }

        sort(seg,seg+n*2);

        //离散化
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());

        //建立线段树，将区间[y1, y2]看成一个点
        build(1,0,ys.size()-2);

        double res=0;
        for(int i=0;i<n*2;i++)
        {
            if(i) res+=tr[1].len*(seg[i].x-seg[i-1].x);
            modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
        }

        printf("Test case #%d\n",T++);
        printf("Total explored area: %.2lf\n\n",res);
    }

    return 0;
}