【题解】【二维线段树】Atlantis(UVALive 2184)-boshi

题意：给定很多个（大概 100 个）矩形，的左上角右下角坐标（不一定为整数），要求它们的面积的并。

分析：这道题的数据非常水，只是 test case 可能会比较多。所以 O(n³) 爆力过不了。只能想想有没有 O(n²log₂n) 或者更低的复杂度的算法。很幸运，有两种可行办法（应该说我只想到了这两种）：第一种是结合扫描线的 O(nlog₂n) 的算法。第二种是二维线段树, 复杂度为约 O(nlog₂n) 其中第一种方案的空间复杂度为 O(nlog₂n) , 第二种为 O(n²log₂n) 。由于数据水的原因，我采用了比较容易想的第二种方案。并且考虑到网上关于二维线段树的题解不多，大量的扫描线，我更坚定了实现二维线段树的信念。

实现：二维线段树的实现很简单，也就是把线段树的两个子节点改成了四个。当然，其时间空间复杂度都会比普通线段树有所增加。下面求其最坏情况下单次操作的时间复杂度。

设一棵二维线段树描述的是一个 n*n 的矩形。则它有 logn 层。

若第 i 层选取了 k 个节点。则第 (i+1) 层最多可以选取 2*k+12 个节点。（显然）若第三层选取了中心的 4 个节点，则第 logn 层选取了约 2^(logn) 个节点。由此推知，二维线段树的最坏单次操作时间复杂度 O(n)。所以方案二的最坏时间复杂度可以退化为 O(n²)，但是对于本题，足矣！

其实二维线段树的用法还不止这种不中用的地方。在二维碰撞检测、矩阵操作等方面它都有用武之地。不多说，上代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

#define MX 501
#define ALL 1
#define SOME 2
#define NO 0

using namespace std;

typedef struct st1
{
    double a1,b1,a2,b2;
    int x1,x2,y1,y2;
}rect;

typedef struct tnode
{
    vector<int> son;
    int l,r,u,d;
    int fa;
    double cv;
    double ar;
    int al;
}treenode;

rect src[MX];
treenode tree[MX*MX*8];
int nnum=0;
double sx[MX],sy[MX];
map<double,int>mpx,mpy;
int n;

int input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&src[i].a1,&src[i].b1,&src[i].a2,&src[i].b2);
    nnum=0;
    return n;
}

void lsh()
{
    int now=1;
    mpx.clear(),mpy.clear();
    for(int i=1;i<=n;i++)mpx[src[i].a1]=1,mpx[src[i].a2]=1,mpy[src[i].b1]=1,mpy[src[i].b2]=1;
    for(map<double,int>::iterator itr=mpx.begin();itr!=mpx.end();itr++,now++)(*itr).second=now;
    now=1;
    for(map<double,int>::iterator itr=mpy.begin();itr!=mpy.end();itr++,now++)(*itr).second=now;
    for(int i=1;i<=n;i++)src[i].x1=mpx[src[i].a1],src[i].x2=mpx[src[i].a2],src[i].y1=mpy[src[i].b1],src[i].y2=mpy[src[i].b2],sx[src[i].x1]=src[i].a1,sx[src[i].x2]=src[i].a2,sy[src[i].y1]=src[i].b1,sy[src[i].y2]=src[i].b2;
}

int build(int x1,int y1,int x2,int y2,int fa)
{
    int node,ret;
    nnum++;
    node=nnum;
    tree[node].l=x1;
    tree[node].r=x2;
    tree[node].u=y2;
    tree[node].d=y1;
    tree[node].ar=(sx[x2+1]-sx[x1])*(sy[y2+1]-sy[y1]);
    tree[node].fa=fa;
    tree[node].cv=0;
    tree[node].al=0;
    tree[node].son.clear();
    if(x1!=x2&&y1!=y2)
    {
        ret=build(x1,y1,(x1+x2)/2,(y1+y2)/2,node);
        tree[node].son.push_back(ret);
        ret=build((x1+x2)/2+1,y1,x2,(y1+y2)/2,node);
        tree[node].son.push_back(ret);
        ret=build(x1,(y1+y2)/2+1,(x1+x2)/2,y2,node);
        tree[node].son.push_back(ret);
        ret=build((x1+x2)/2+1,(y1+y2)/2+1,x2,y2,node);
        tree[node].son.push_back(ret);
    }
    else if(x1!=x2&&y1==y2)
    {
        ret=build(x1,y1,(x1+x2)/2,y2,node);
        tree[node].son.push_back(ret);
        ret=build((x1+x2)/2+1,y1,x2,y2,node);
        tree[node].son.push_back(ret);
    }
    else if(x1==x2&&y1!=y2)
    {
        ret=build(x1,y1,x2,(y1+y2)/2,node);
        tree[node].son.push_back(ret);
        ret=build(x1,(y1+y2)/2+1,x2,y2,node);
        tree[node].son.push_back(ret);
    }
    else if(x1==x2&&y1==y2);
    return node;
}

void pushdown(int node)
{
    if(tree[node].al)
    {
        for(unsigned int i=0;i<tree[node].son.size();i++)
        {
            tree[tree[node].son[i]].al=1;
            tree[tree[node].son[i]].cv=tree[tree[node].son[i]].ar;
        }
        tree[node].al=0;
    }
}

void update(int node)
{
    tree[node].cv=0;
    for(unsigned int i=0;i<tree[node].son.size();i++)tree[node].cv+=tree[tree[node].son[i]].cv;
}

void add(int node,int x1,int y1,int x2,int y2)
{
    pushdown(node);
    int a1,a2,b1,b2;
    a1=tree[node].l;
    a2=tree[node].r;
    b1=tree[node].d;
    b2=tree[node].u;
    if(x1<=a1&&a2<=x2&&y1<=b1&&b2<=y2)
    {
        tree[node].cv=tree[node].ar;
        tree[node].al=1;
    }
    else if(a1>x2||a2<x1||b1>y2||b2<y1);
    else
    {
        for(unsigned int i=0;i<tree[node].son.size();i++)add(tree[node].son[i],x1,y1,x2,y2);
        update(node);
    }
}

int main()
{
    int cas=0;
    while(input()!=0)
    {
        lsh();
        build(1,1,n*2-1,n*2-1,0);
        for(int i=1;i<=n;i++)add(1,src[i].x1,src[i].y1,src[i].x2-1,src[i].y2-1);
        cout<<"Test case #"<<++cas<<endl;
        printf("Total explored area: %.2f\n\n",tree[1].cv);
    }
    return 0;
}

纪念以下这道水过的水题