线段树之离散化

POJ - 2528

离散化是将有用的信息提取出来，在区间很大的时候，用直接用线段树肯定会超时，但由于在区间内很大值是没有用到的，只把有用的区间提取出来再用线段数做就方便多了。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define lson l,m,rt<<1
 6 #define rson m+1,r,rt<<1|1
 7 using namespace std;
 8 const int MAX = 11111;
 9 int col[MAX<<4],li[MAX],ri[MAX],x[MAX*3],ans;
10 bool hash[MAX];
11 void PushDown(int rt){
12     if(col[rt] != -1){
13         col[rt<<1] = col[rt<<1|1] = col[rt];
14         col[rt] = -1;
15     }
16 }
17 void update(int LL, int RR, int c, int l, int r, int rt){
18     if(LL <= l && r <= RR){
19         col[rt] = c;
20         return;
21     }
22     PushDown(rt);
23     int m = (l+r)>>1;
24     if(LL <= m)update(LL,RR,c,lson);
25     if(m < RR) update(LL,RR,c,rson);
26 }
27 void query(int l, int r, int rt){
28     if(col[rt] != -1){
29         if(!hash[col[rt]])ans++;
30         hash[col[rt]] = true;
31         return;
32     }
33     if(l == r)return;
34     int m = (l+r)>>1;
35     query(lson);
36     query(rson);
37 }
38 int Bin(int key,int len){
39     int l = 0, r = len-1;
40     while(l <= r){
41         int m = (l+r)>>1;
42         if(x[m] == key)return m;
43         if(x[m] > key)r = m-1;
44         else l = m+1;
45     }
46     return -1;
47 }
48 int main(){
49     int t,n;
50     scanf("%d",&t);
51     while(t--){
52         scanf("%d",&n);
53         int nn = 0;
54         for(int i = 0; i < n; i ++){
55             scanf("%d %d",&li[i],&ri[i]);
56             x[nn++] = li[i];x[nn++] = ri[i];
57         }
58         sort(x,x+nn);
59         int m = 1;
60         for(int i = 1; i < nn; i ++){
61             if(x[i]!=x[i-1])x[m++] = x[i];
62         }
63         for(int i = m-1; i > 0; i --){
64             if(x[i] != x[i-1]+1)x[m++] = x[i-1]+1;
65         }
66         sort(x,x+m);
67         memset(col,-1,sizeof(col));
68         for(int i = 0; i < n; i ++){
69             int l = Bin(li[i],m);
70             int r = Bin(ri[i],m);
71             update(l,r,i,0,m,1);
72         }
73         ans = 0;
74         memset(hash,false,sizeof(hash));
75         query(0,m,1);
76         printf("%d
",ans);
77     }
78     return 0;
79 }