有一面墙，被等分为1QW份，一份的宽度为一个单位宽度。现在往墙上贴N张海报，每张海报的宽度是任意的，但是必定是单位宽度的整数倍，且<=1QW。后贴的海报若与先贴的海报有交集，后贴的海报必定会全部或局部覆盖先贴的海报。现在给出每张海报所贴的位置（左端位置和右端位置），问张贴完N张海报后，还能看见多少张海报？（PS：看见一部分也算看到。）

/*

 * my_poj2528.cpp

 *

 *  Created on: 2012-6-15

 *      Author: ict

 */

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

using namespace std;

#define MAX 20010

#define LC(x) ((x) << 1) //计算左孩子位置

#define RC(x) (((x) << 1) + 1) //计算右孩子位置

struct Node

{

int l; //线段左端点值

int r; //线段右端点

int c; //线段的颜色

}nodes[MAX * 5];

int map[MAX][2]; //记录输入线段的左右两个端点

int record[MAX]; //记录颜色是否已经出现

int total;

//用于离散化

struct Line

{

int point; //记录端点的坐标

int num; //记录原来的编号

}line[MAX * 2];

int mycmp(const Line &a, const Line &b)

{

return a.point < b.point;

}

void buildTree(int l, int r, int position)//buildTree(1, count, 1);

{

nodes[position].l = l;

nodes[position].r = r;

nodes[position].c = 0; //初始化颜色都为0

if(l == r)

return ;

int mid = (l + r) >> 1;

buildTree(l, mid, LC(position)); //构造左子树

buildTree(mid + 1, r, RC(position)); //构造右子树

return ;

}

/*

 * @para l, r: 线段的左、右端点

 * @para position: 插入树的位置

 * @para color: 线段的颜色

 */

void insert(int l, int r, int position, int color)//insert(map[i][0], map[i][1], 1, i + 1);第i个海报对应i+1号色

{

if(nodes[position].l == l && nodes[position].r == r) //刚好覆盖，修改颜色，直接返回

{

nodes[position].c = color;

return ;

}

if(nodes[position].c > 0) //pushdown

{

nodes[LC(position)].c = nodes[position].c;

nodes[RC(position)].c = nodes[position].c;

nodes[position].c = 0; // 这就是pushup，父节点颜色是混乱的，用0表示

}

if(l >= nodes[RC(position)].l) //完全在右子树

insert(l, r, RC(position), color);

else

if(r <= nodes[LC(position)].r) //完全在左子树

insert(l, r, LC(position), color);

else //两个子树都有

{

insert(l, nodes[LC(position)].r, LC(position), color);

insert(nodes[RC(position)].l, r, RC(position), color);

}

}

/*

 * @para position: 查询指定线段的颜色

 */

void update(int position)

{

if(nodes[position].c != 0) //整个根节点以下是同一个颜色，统计该色

{

if(!record[nodes[position].c])//是否存在过

{

total++;

record[nodes[position].c] = 1;

}

return ;

}

//不是同一个颜色，是混合的

update(LC(position));

update(RC(position));

return ;

}

int main()

{

int number;

int n;

int i;

scanf("%d", &number);

while(number--)

{

scanf("%d", &n);

for(i = 0; i < n; i++)

{

scanf("%d%d", &map[i][0], &map[i][1]);

line[2*i].point = map[i][0]; //记录数据，用于离散化

line[2*i + 1].point = map[i][1];

line[2*i].num = -(i + 1); //线段第一个端点用负数记录

line[2*i + 1].num = i + 1; //线段第二个端点用正数记录

}

//首先将所有端点排序

sort(line, line + 2*n, mycmp);

int temp = line[0].point;

int count = 1; //重新开始编号，从1开始

for(i = 0; i < 2*n; i++)

{

if(temp != line[i].point) //如果当前端点和前面的端点不一样，编号值+1

{

count++;

temp = line[i].point;

}

/*离散就要考虑去重。这里离散的过程：

map  : [-3,2] [-1,4]  [-2,-1] 表示map[0][0]=-3,map[0][1]=2

line.point: [-3,2] [-1,4]  [-2,-1] 表示line.point[0]=-3 line.point[1]=2

line.num: [-1,1] [-2,2]  [-3,3]  表示line.num[0]=-1,line.num[1]=1

sort后,line.point:  [-3,-2][-1,-1] [2,4]

sort后，line.num:   [-1,-3][-2,3]  [1,2]   

得到新的map:        [1,4]  [3,5]    [2,3]

对应旧的map         [-3,2] [-1,4]  [-2,-1]，大小相对关系不变，次序也不变

其实跟一维离散一样的道理，point记录原始值大小，num记录本来的次序

根据point排序后，用map[-line[i].num - 1][0] = count离散

其中，-line[i].num - 1表示以前处于什么次序，现在还在那个次序

count去除重复后，从1递增，因为排序后line[i].point也是递增，即以前大小

排第几，现在还是排第几

  */

if(line[i].num < 0)

map[-line[i].num - 1][0] = count;

else

map[line[i].num - 1][1] = count;

}

buildTree(1, count, 1);

for(i = 0; i < n; i++)//按次序插入

insert(map[i][0], map[i][1], 1, i + 1);

memset(record, 0, sizeof(record));

total = 0;

update(1);

printf("%d\n", total);

}

return 0;

}

TreeSegment2528