http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
這是一道經(jīng)典的線段樹題目，另外加上離散化的方法。
離散化：由于題目中wall有10000000bytes long，直接線段樹無疑會MLE。所以要對其離散化，基本做法是：先對所有端點坐標進行排序，用相應序號代替端點坐標構(gòu)造線段樹進行計算。這樣最大的序號也只是2*n。
在構(gòu)造線段樹的節(jié)點結(jié)構(gòu)體時，添加變量c。c=0時表示c線段沒有貼海報，或者貼了不止一張海報；c>0時表示貼了一張海報，并且c的值表示貼的是第幾張海報。
線段樹更新的基本原理就是，當我們貼海報i時，如果遇到某一線段區(qū)間能夠被當前海報完全覆蓋，那么我們更新到此區(qū)間即可，即讓它的變量c更新為海報i，記錄下i的值。如果不能被海報完全覆蓋，則只是這一線段區(qū)間的部分區(qū)間需要修改，則更改這一區(qū)間的子區(qū)間即可。
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);//用負數(shù)表示 線段起點
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