[线段树][扫描线][面积并] HDU1542 Atlantis

扫描线第一题，求矩形面积的并。思路很好理解，但是实现上有很多的问题。

1 维护的变量ala[o]代表含义是“当前节点对应区间全覆盖的点数”，举个例子来说，现在的区间各个节点的值如果是2 3 3 3 5 5 2，那么ala就应该是2。这个变量这么做的好处就是，当ala不为0的时候一定可以直接把整个区间的Len算出来：就是x[r]-x[l]，当他为0的时候说明中间有的点为0，那么我们再考虑左右儿子Len之和。这个东西注意是不要pushdown的，如果pushdown了反而会使得问题变得复杂，因为如果你只是往里面+1也要pushdown的话，那等于原来的可以直接得到的Len现在反而要往下走才可以得到。那么不pushdown会不会出现重复加的情况？也不会，因为这个问题里所有的形状都是矩形，有一个上下边使得ala[o]+1，则一定有另外一个边使得他-1，而这中间的呢？因为肯定这一条线段都是还是属于计算范围的，所以也没有多加，一定是对的，这个特点很重要，今早赖床的时候想了下才明白其中的奥妙所在。。。。

引用一位dalao的话描述一下

这里的区间覆盖不需要打懒惰标记。为什么呢？因为很显然，每个下边都有与之对应的上边，它显然不会被比它的长度小的上边给清除。而如果有比它长的上边，也一定有和那个上边对应的下边还存在。所以用那个上边清除下边的时候，一定会先递归到那个更长的下边，还没有递归到它就停止递归了。所以每个上下边是一一对应的，无需下传标记等。

2 这个线段树不是[l,r]，而是[l,r)，因为我们这里离散化之后，如果按照闭区间来算，那[mid,mid+1]这一段就不能被计算到了，所以要用左闭右开，这样的话对应的一开始的区间右边要+1，而这样又会有问题就是原来的整个线段，也就是o==1时候的线段，以及所有的右侧端点为整个线段树右端点的线段，他们的右侧怎么处理，这可是个必须要左闭右闭的啊？我这里用的是在xs离散化数组的后面加上一个和xs[cnt1]相等的元素，这样就可以不用特殊判断了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;

typedef long long LL;
const int maxn =132674*2+10;

struct seg
{
    double x1,x2,y;
    int flag;
    bool operator<(const struct seg &rhs)const {return y<rhs.y;}
} segs[205];

// discretize
int cnt1;
double xs[205];
int Hash(double m)
{
    return lower_bound(xs+1,xs+1+cnt1,m)-xs;
}

double Len[maxn<<2];
int ala[maxn<<2];

void maintain(int o,int l,int r)
{
    if(l==r)//empty segment
        Len[o]=0.0;
    else if(ala[o]>0)
        Len[o]=(xs[r]-xs[l]);
    else
        Len[o]=Len[o<<1]+Len[o<<1|1];
}

int pl,pr,v;
void update(int o,int l,int r)//[l,r)
{
    if(l>r-1)//[l,r)
        return ;
    if(pl<=l&&r<pr)
    {
        ala[o]+=v;
    }
    else if(l!=r-1)//not leaf node
    {
        //pushdown(o,l,r);//do not pushdown for the property of the problem
        int mid=(l+r)>>1;
        if(pl<mid)
            update(o<<1,l,mid);
        if(mid<pr)
            update(o<<1|1,mid,r);
    }
    maintain(o,l,r);
}

int main()
{
    int T,cs=0,n;
    double x1,y1,x2,y2,ans,h;
    while(~scanf("%d",&n)&&n)
    {
        memset(ala,0,sizeof(ala));
        memset(Len,0,sizeof(Len));//error1
        ans=0.0;
        cs++;
        cnt1=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xs[++cnt1]=x1,xs[++cnt1]=x2;
            segs[2*i-1].x1=x1,segs[2*i-1].x2=x2,segs[2*i-1].y=y1,segs[2*i-1].flag=1;
            segs[2*i].x1=x1,segs[2*i].x2=x2,segs[2*i].y=y2,segs[2*i].flag=-1;
        }
        sort(segs+1,segs+1+2*n);
        sort (xs+1,xs+1+cnt1);
        cnt1=1;
        for (int i=2; i<=2*n; i++)
            if (xs[i]!=xs[cnt1])
                xs[++cnt1]=xs[i];
        
        xs[cnt1+1]=xs[cnt1];//[l,r)
        for (int i=1;i<((n<<1));i++)
        {
            h=segs[i+1].y-segs[i].y;
            v=segs[i].flag;
            pl=Hash(segs[i].x1),pr=Hash(segs[i].x2)+1;
            update(1,1,cnt1+1);
            ans+=Len[1]*h;
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",cs,ans);
    }
    return 0;
}