POJ 2528 Mayor's posters 线段树+离散化

 1 const int maxn = 1e4 + 5;
 2 int hash[10000005];
 3 int tree[maxn * 8], n;
 4 int st[maxn], ed[maxn], pos[maxn * 2];
 5 int vis[maxn];
 6 
 7 void build(int l, int r, int k){
 8     tree[k] = -1;
 9     if(l == r) return;
10     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
11     build(l, mid, lc);
12     build(mid + 1, r, rc);
13 }
14 void update(int ul, int ur, int x, int l, int r, int k){
15     if(ul <= l && ur >= r){
16         if(tree[k] == -1)
17             tree[k] = x;
18         return;
19     }
20     if(ul > r || ur < l) return;
21     if(l == r){
22         if(tree[k] == -1) tree[k] = x;
23         return;
24     }
25     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
26     if(tree[k] != -1){
27         if(tree[lc] == -1) tree[lc] = tree[k];
28         if(tree[rc] == -1) tree[rc] = tree[k];
29         tree[k] = -1;
30     }
31     
32     update(ul, ur, x, l, mid, lc);
33     update(ul, ur, x, mid + 1, r, rc);
34 }
35 int query(int qu, int l, int r, int k){
36     if(qu == l && l == r){
37         return tree[k];
38     }
39     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
40     if(tree[k] != -1){
41         if(tree[lc] == -1) tree[lc] = tree[k];
42         if(tree[rc] == -1) tree[rc] = tree[k];
43         tree[k] = -1;
44     }
45     
46     if(qu <= mid) return query(qu, l, mid, lc);
47     else return query(qu, mid + 1, r, rc);
48 }
49 int main(){
50     int T;
51     scanf("%d", &T);
52     while(T--){
53         memset(hash, -1, sizeof(hash));
54         memset(vis, 0, sizeof(vis));
55         scanf("%d", &n);
56         int cnt = 0;
57         for(int i = 0; i < n; i++){
58             scanf("%d %d", &st[i], &ed[i]);
59             pos[cnt++] = st[i];
60             pos[cnt++] = ed[i];
61         }
62         sort(pos, pos + cnt);
63         cnt = unique(pos, pos + cnt) - pos;
64         for(int i = 1; i <= cnt; i++)
65             hash[pos[i - 1]] = i;
66         build(1, cnt, 1);
67         for(int i = n - 1; i >= 0; i--){
68             update(hash[st[i]], hash[ed[i]], i + 1, 1, cnt, 1);
69         }
70         for(int i = 1; i <= cnt; i++){
71             int tmp = query(i, 1, cnt, 1);
72             if(tmp != -1) vis[tmp] = 1;
73         }
74         int ans = 0;
75         for(int i = 1; i <= n; i++) ans += vis[i];
76         printf("%d\n", ans);
77     }
78 }