http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
这是一道经典的线段树题目，另外加上离散化的方法。
离散化：由于题目中wall有10000000bytes long，直接线段树无疑会MLE。所以要对其离散化，基本做法是：先对所有端点坐标进行排序，用相应序号代替端点坐标构造线段树进行计算。这样最大的序号也只是2*n。
在构造线段树的节点结构体时，添加变量c。c=0时表示c线段没有贴海报，或者贴了不止一张海报；c>0时表示贴了一张海报，并且c的值表示贴的是第几张海报。
线段树更新的基本原理就是，当我们贴海报i时，如果遇到某一线段区间能够被当前海报完全覆盖，那么我们更新到此区间即可，即让它的变量c更新为海报i，记录下i的值。如果不能被海报完全覆盖，则只是这一线段区间的部分区间需要修改，则更改这一区间的子区间即可。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<string.h>
5 #define MAX 20001
6
7 using namespace std;
8
9 int c,n,ls[MAX];
10 struct node{
11 int l,r;
12 int c;
13 }tree[MAX*4];
14 struct ln{
15 int li,num;//num表示第几张海报
16 }line[MAX];
17 int set[MAX][2];
18 bool visit[MAX];
19 int ans;
20
21 bool cmp(struct ln a,struct ln b){
22 return a.li<b.li;
23 }
24
25 void Inittree(int pos,int ll,int rr){
26 tree[pos].l = ll;
27 tree[pos].r = rr;
28 tree[pos].c = 0;
29 if(ll!=rr){
30 int mid = (ll+rr)>>1;
31 Inittree(pos*2,ll,mid);
32 Inittree(pos*2+1,mid+1,rr);
33 }
34 }
35
36 void Insert(int pos,int ll,int rr,int color){
37 if(tree[pos].l == ll && tree[pos].r == rr){
38 tree[pos].c = color;
39 return;
40 }
41 if(tree[pos].c > 0 && tree[pos].c != color){
42 tree[pos*2].c = tree[pos].c;
43 tree[pos*2+1].c = tree[pos].c;
44 tree[pos].c = 0;
45 }
46 int mid = (tree[pos].l + tree[pos].r)>>1;
47 if(rr<=mid){
48 Insert(pos*2,ll,rr,color);
49 }
50 else if(ll>mid){
51 Insert(pos*2+1,ll,rr,color);
52 }
53 else{
54 Insert(pos*2,ll,mid,color);
55 Insert(pos*2+1,mid+1,rr,color);
56 }
57 }
58
59 void Search(int pos){
60 if(tree[pos].c!=0){
61 if(!visit[tree[pos].c]){//tree[pos].c
62 visit[tree[pos].c] = true;
63 ans++;
64 }
65 return ;
66 }
67 Search(2*pos);
68 Search(2*pos+1);
69 }
70
71 int main()
72 {
73 int i;
74 while(scanf("%d",&c)!=EOF){
75 while(c--){
76 scanf("%d",&n);
77 for(i = 0;i < n;++i){//离散化
78 scanf("%d%d",&set[i][0],&set[i][1]);
79 line[2*i].li = set[i][0];
80 line[2*i].num = -(i+1);//用负数表示 线段起点
81 line[2*i+1].li = set[i][1];
82 line[2*i+1].num = i+1;
83 }
84 sort(line,line+2*n,cmp);
85 int temp = line[0].li,tp = 1;
86 for(i = 0;i < 2*n;++i){
87 if(line[i].li != temp){
88 tp++;
89 temp = line[i].li;
90 }
91 if(line[i].num < 0){
92 set[-line[i].num-1][0] = tp;
93 }
94 else{
95 set[line[i].num-1][1] = tp;
96 }
97 }//离散化
98
99 Inittree(1,1,tp);
100 for(i = 0;i < n;++i){
101 Insert(1,set[i][0],set[i][1],i+1);
102 }
103 memset(visit,0,sizeof(visit));
104 ans = 0;
105 Search(1);
106 printf("%d\n",ans);
107 }
108 }
109 return 0;
110 }
111