[线段树][扫描线][面积交] HDU 1255

这次写了这个题目之后我发现之前对面积并的那个cal计数的意义还是理解还是有一点偏差：这个东西表示的是当前节点对应的线段整体覆盖的情况。为0时没有被全覆盖（注意不等于没有被覆盖），为1时被全覆盖了1次（意为min(l,r)==1，不代表不大于1)，为k时表示min(l,r)==k。而且对应的只是一个节点对应的整个线段，跟只表示当前整段线段的状况，儿子是什么样不知道。。。

这个题也貌似有很多种方法，我参考了一位前辈的博客之后用了Len1表示全覆盖次数≥1的长度，Len2表示全覆盖次数≥2的长度，当然全部都是针对当前节点。Len1的维护方法和面积并的方法完全一样。然后Len2维护的时候就是，如果cnt[o]大于等于2，那么说明当前节点被全覆盖了两次，直接Len2=Len1，如果为1，说明当前节点被全覆盖了一次，那么只需要加上子节点中被全覆盖了一次的Len1就可以了（这样相当于在双亲节点里覆盖了两次），如果是叶子节点，没有孩子，那就直接是0，如果cnt为0，那就只有孩子里面的被全覆盖了两次之和才能更新当前点了。
这里还有一个需要注意的是，如果cnt为0，那么要么说明，当前节点从来没有被计算过，要么说明只计算过子节点，所以不会出现错误。

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<unordered_set>
#include<unordered_map>
#define eps 1e-6
//#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e3+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

struct seg
{
    double lt,rt,y;
    int flag;
    seg(){};
    bool operator<(const struct seg &rhs)const {return y<rhs.y;}
}segs[maxn<<1];
int n,cntx,cnty;
double xs[maxn<<1],ys[maxn<<1];

int getX(double x){return lower_bound(xs+1,xs+1+cntx,x)-xs;}
int getY(double y){return lower_bound(ys+1,ys+1+cnty,y)-ys;}

double Len1[maxn<<4],Len2[maxn<<4];
int cnt[maxn<<4];

void maintain(int o,int l,int r)//[l,r)
{
    if(cnt[o])
        Len1[o]=xs[r]-xs[l];
    else
        Len1[o]=Len1[o<<1]+Len1[o<<1|1];

    if(cnt[o]>1)
        Len2[o]=Len1[o];
    else if(cnt[o]==1&&l<r-1)
        Len2[o]=Len1[o<<1]+Len1[o<<1|1];//the most important
    else if(cnt[o]==1&&l==r-1)
        Len2[o]=0.0;
    else
        Len2[o]=Len2[o<<1]+Len2[o<<1|1];
}


int pl,pr,v;
void update(int o,int l,int r)
{
    if(l==r)return ;
    if(pl<=l&&r<pr)
    {
        cnt[o]+=v;
    }
    else if(l!=r-1)
    {
        int mid=(l+r)>>1;
        if(pl<mid)update(o<<1,l,mid);
        if(mid<pr)update(o<<1|1,mid,r);
    }
    /*有没有return都一样
    else
    {
        return ;
    }
    */
    maintain(o,l,r);
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T;
    double x1,x2,y1,y2;
    scanf("%d",&T);
    while(T--)
    {
        memset(Len1,0,sizeof(Len1));
        memset(Len2,0,sizeof(Len2));
        memset(cnt,0,sizeof(cnt));
        cntx=cnty=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xs[++cntx]=x1,xs[++cntx]=x2;
            ys[++cnty]=y1,ys[++cnty]=y2;
            segs[2*i-1].lt=x1,segs[2*i-1].rt=x2,segs[2*i-1].y=y1,segs[2*i-1].flag=1;
            segs[i<<1].lt=x1,segs[i<<1].rt=x2,segs[i<<1].y=y2,segs[i<<1].flag=-1;
        }
        sort(segs+1,segs+1+2*n);
        sort(xs+1,xs+1+2*n);
        sort(ys+1,ys+1+2*n);
        cntx=cnty=1;
        for (int i=2;i<=2*n;i++)
        {
            if(xs[i]!=xs[cntx])
                xs[++cntx]=xs[i];
            if(ys[i]!=ys[cnty])
                ys[++cnty]=ys[i];
        }
        xs[cntx+1]=xs[cntx];
        ys[cnty]=ys[cnty];
        double ans=0.0;
        for (int i=1;i<2*n;i++)
        {
            double ch=segs[i+1].y-segs[i].y;
            pl=getX(segs[i].lt),pr=getX(segs[i].rt)+1,v=segs[i].flag;
            update(1,1,cntx+1);
            ans+=Len2[1]*(ch);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}