学步园

http://poj.org/problem?id=2528

题意：

市长竞选，每个市长都往墙上贴海报，海报之间彼此可以覆盖，给出粘贴顺序和每个海报的起点和终点，问最后又多少海报时可见的。

刚接触离散化，先写一写本人的理解：

如果原数据太大，建树会超内存。因此可以先对这些数排序，然后将它们映射成排序后的序号。比如在该题中，[1,4],[2,6],[8,10],[3,4],[7,10]； 先对这些区间端点去重（离散化要注意这一点，可以节省空间）排序后得  1,2,3,4,6,7,8,10 ；那么可以将这些数映射成其对应编号：

1        2        3        4        6        7         8        10

1        2        3        4        5        6         7         8

那么原区间就变成[1,4],[2,5],[7,8],[3,4],[6,8]； 这样建树只需要 8的空间，按区间端点数值建树需要10的空间。。如果数据更大，经过离散后会大大节省空间。

思路：

由于wall最大是1000 0000，直接用线段端点坐标建树肯定超内存。所以就像上面说的先离散化，再建树。之后，再从第一张开始贴，每贴一张就去更新相应区间的kind值。最后递归统计有多少个不同的kind值即可。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int maxn = 10005;

//定义线段树节点
struct line
{
    int l;
    int r;
    int kind;//kind=0表示该线段没有贴海报或贴了不止一张海报，kind>0表示贴了一张海报，其值为贴点的第几张海报
}tree[10*maxn];

//用于离散化，将每个坐标绑定一个编号，最多2*maxn个坐标
struct item
{
    int coord;
    int id;
}poster[2*maxn];

int n;
int l[maxn],r[maxn];//记录每个区间的左右端点
bool mark[maxn];//在最后统计时用，统计过的节点为true
int result;

int cmp(const void * p, const void *q)
{
    return ((item*)p)->coord - ((item*)q)->coord;
}

//建树。
void build(int v, int l, int r)
{
    tree[v].l = l;
    tree[v].r = r;
    if(l == r)
        return;
    int mid = (l+r)>>1;

    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

//更新，
void update(int v, int l, int r, int cover)
{
	//当贴海报i时，如果遇到某一区间能够被当前海报完全覆盖，那么更新到此区间，即让它的变量kind涂上cover色
    if(tree[v].l == l && tree[v].r == r)
    {
        tree[v].kind = cover;
        return;
    }
    
	//特别注意，如果该区间v已被覆盖且与cover不同，必须先将v的左右儿子更改成v的类型，然后v本身变成0
    if(tree[v].kind != 0 && tree[v].kind != cover)
    {
        tree[v*2].kind = tree[v].kind;
        tree[v*2+1].kind = tree[v].kind;
        tree[v].kind = 0;
    }

    int mid = (tree[v].l+tree[v].r)>>1;
    if(r <= mid)
        update(v*2,l,r,cover);	//更新左子树
    else if(l > mid)
        update(v*2+1,l,r,cover); //更新右子树
    else
    {
        update(v*2,l,mid,cover);
        update(v*2+1,mid+1,r,cover); //左右子树均需更新
    }
}

void cal(int v)
{
    if(tree[v].kind != 0) //表明被覆盖
    {
        if(mark[tree[v].kind] == false)	//表明未被统计过
        {
            mark[tree[v].kind] = true;	//标记已统计
            result += 1;
        }
    }
    else
    {
        cal(2*v);
        cal(2*v+1);
    }

}

int main()
{
    int test;
    int i,j;
    struct item *tmpl,*tmpr,tl,tr;
    scanf("%d",&test);
    while(test--)
    {
        memset(tree,0,sizeof(tree));
        memset(mark,false,sizeof(mark));
        memset(poster,0,sizeof(poster));
        scanf("%d",&n);
        for(i = 1,j = 1; i <= n; i++)
        {
            scanf("%d %d",&l[i],&r[i]);
            poster[j++].coord = l[i];
            poster[j++].coord = r[i];	//把每一幅海报的坐标都记录下来，不分左右，以便离散化
        }

        qsort(poster+1,2*n,sizeof(item),cmp);

        for(i = 1,j = 1; i <= 2*n; i++,j++)
        {
            poster[j].coord = poster[i].coord;
            poster[j].id = j;	//每个坐标绑定一个编号
            while(poster[i].coord == poster[i+1].coord) ++i;//删除重复坐标，因为相同坐标只需遍一个号即可
        }
        
        build(1,1,j-1); 		//建树

        for(i = 1; i <= n; i++)
        {
            tl.coord = l[i];
            tr.coord = r[i];	//tl,tr是同一条线段的两个端点
			
			//二分找出t1,t2的地址，以便找出其编号
            tmpl = (item*)bsearch(&tl,poster+1,j,sizeof(item),cmp);
            tmpr = (item*)bsearch(&tr,poster+1,j,sizeof(item),cmp);

            update(1,tmpl->id,tmpr->id,i);//插入两个编号构成的线段，更新
        }

        result = 0;
        cal(1);	//统计，从根节点1开始
        printf("%d\n",result);
    }
    return 0;
}

1、  线段树是二叉树，且必定是平衡二叉树，但不一定是完全二叉树。

2、  对于区间[a,b]，令mid=(a+b)/2，则其左子树为[a,mid]，右子树为[mid+1,b]，当a==b时，该区间为线段树的叶子，无需继续往下划分。

3、  线段树虽然不是完全二叉树，但是可以用完全二叉树的方式去构造并存储它，只是最后一层可能存在某些叶子与叶子之间出现“空叶子”，这个无需理会，同样给空叶子按顺序编号，在遍历线段树时当判断到a==b时就认为到了叶子，“空叶子”永远也不会遍历到。

4、  之所以要用完全二叉树的方式去存储线段树，是为了提高在插入线段和搜索时的效率。用p*2，p*2+1的索引方式检索p的左右子树要比指针快得多。

5、线段树的精髓是，能不往下搜索，就不要往下搜索，尽可能利用子树的根的信息去获取整棵子树的信息。如果在插入线段或检索特征值时，每次都非要搜索到叶子，还不如直接建一棵普通树更来得方便。