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、线段树的精髓是，能不往下搜索，就不要往下搜索，尽可能利用子树的根的信息去获取整棵子树的信息。如果在插入线段或检索特征值时，每次都非要搜索到叶子，还不如直接建一棵普通树更来得方便。
poj 2528 Mayor's posters(离散化+线段树)
原文：http://blog.csdn.net/u013081425/article/details/19046067