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