poj 2828 Buy Tickets

　　个人选拔的时候的题目，今天看来是水的不得了啊！~不过因为忘记换行了，搞了两个PE回来....囧...以后会注意的了。

　　题目意思不难明白，不过用线段树写要将数据倒过来处理，这样才能得到目标队列！

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1 | 1
 7 
 8 const int maxn = 200001;
 9 int cnt[maxn << 2], mk[maxn << 2];
10 int bf1[maxn], bf2[maxn];
11 bool pr;
12 
13 void up(int rt){
14     cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
15 }
16 
17 void build(int l, int r, int rt){
18     if (l == r){
19         cnt[rt] = 1;
20         return ;
21     }
22     int m = (l + r) >> 1;
23 
24     build(lson);
25     build(rson);
26     up(rt);
27 }
28 
29 void ins(int p, int key, int l, int r, int rt){
30     if (l == r){
31         mk[rt] = key;
32         cnt[rt] = 0;
33         return ;
34     }
35     int m = (l + r) >> 1;
36 
37     if (p <= cnt[rt << 1]) ins(p, key, lson);
38     else ins(p - cnt[rt << 1], key, rson);
39     up(rt);
40 }
41 
42 void print(int l, int r, int rt){
43     if (l == r){
44         if (pr) putchar(' ');
45         pr = true;
46         printf("%d", mk[rt]);
47 
48         return ;
49     }
50 
51     int m = (l + r) >> 1;
52 
53     print(lson);
54     print(rson);
55 }
56 
57 void deal(int n){
58     build(1, n, 1);
59     for (int i = 0; i < n; i++){
60         scanf("%d%d", &bf1[i], &bf2[i]);
61     }
62     for (int i = n - 1; i >= 0; i--){
63         ins(bf1[i] + 1, bf2[i], 1, n, 1);
64     }
65     pr = false;
66     print(1, n, 1);
67     puts("");
68 }
69 
70 int main(){
71     int n;
72 
73     while (~scanf("%d", &n)){
74         deal(n);
75     }
76 
77     return 0;
78 }

——written by Lyon