POJ 2828 Buy Tickets（神题！线段树or树状数组）

 1 /*
 2 ** POJ 2828 Buy Tickets
 3 ** Created by Rayn @@ 2014/05/08
 4 ** 神奇线段树，奇妙的逆向思维
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 using namespace std;
10 const int MAX = 200005;
11 
12 int pos[MAX], val[MAX], ans[MAX];
13 int tree[MAX*3], index;
14 
15 void Build(int k, int l, int r)
16 {
17     tree[k] = r - l + 1;    //开始时每个节点都有空位
18     if(l == r)
19         return ;
20     int mid = (l + r) >> 1;
21     Build(k<<1, l, mid);
22     Build(k<<1|1, mid+1, r);
23 }
24 void Update(int k, int l, int r, int pos)
25 {
26     tree[k]--;  //单点更新，减少一个空位
27     if(l == r)
28     {
29         index = l;
30         return ;
31     }
32     int mid = (l + r) >> 1;
33     if(tree[k<<1] >= pos)   //如果当前位置的左边空位够的话就落在左边
34     {
35         Update(k<<1, l, mid, pos);
36     }
37     else
38     {
39         pos -= tree[k<<1];  //否则，就把左边的空位减去，再在右边定位
40         Update(k<<1|1, mid+1, r, pos);
41     }
42 }
43 int main()
44 {
45 #ifdef _Rayn
46     freopen("in.txt", "r",stdin);
47 #endif
48     int n;
49     while(scanf("%d", &n) != EOF)
50     {
51         Build(1, 1, n);
52         for(int i=1; i<=n; ++i)
53         {
54             scanf("%d%d", &pos[i], &val[i]);
55         }
56         for(int i=n; i>=1; --i)
57         {
58             Update(1, 1, n, pos[i]+1);
59             ans[index] = val[i];
60         }
61         for(int i=1; i<=n; ++i)
62         {
63             printf("%d%c", ans[i], (i == n)? ‘\n‘:‘ ‘);
64         }
65     }
66     return 0;
67 }

 1 /*
 2 ** POJ 2828 Buy Tickets
 3 ** Created by Rayn @@ 2014/05/08
 4 ** 树状数组+二分
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 using namespace std;
10 const int MAX = 200005;
11 
12 int n, pos[MAX], val[MAX];
13 int tree[MAX], ans[MAX];
14 
15 inline int Lowbit(int x)
16 {
17     return x&(-x);
18 }
19 int GetSum(int idx)
20 {
21     int sum = 0;
22     while(idx > 0)
23     {
24         sum += tree[idx];
25         idx -= Lowbit(idx);
26     }
27     return sum;
28 }
29 void Update(int idx, int val)
30 {
31     while(idx <= n)
32     {
33         tree[idx] += val;
34         idx += Lowbit(idx);
35     }
36 }
37 int Search(int left, int right, int pos)
38 {
39     while(left <= right)
40     {
41         int mid = (left + right) >> 1;
42         int tmp = GetSum(mid);
43         if(tmp == pos && ans[mid] == -1)
44             return mid;
45         if(tmp >= pos)
46             right = mid - 1;
47         else
48             left = mid + 1;
49     }
50     return -1;
51 }
52 int main()
53 {
54 #ifdef _Rayn
55     freopen("in.txt", "r",stdin);
56 #endif
57 
58     while(scanf("%d", &n) != EOF)
59     {
60         memset(tree, 0, sizeof(tree));
61         memset(ans, -1, sizeof(ans));
62         for(int i=1; i<=n; ++i)
63         {
64             scanf("%d%d", &pos[i], &val[i]);
65             pos[i]++;
66             Update(i, 1);    //所有位置填充1，代表有空位
67         }
68         for(int i=n; i>=1; --i)
69         {
70             int index = Search(pos[i], n, pos[i]);
71             ans[index] = val[i];
72             Update(index, -1);
73         }
74         for(int i=1; i<=n; ++i)
75         {
76             printf("%d%c", ans[i], (i == n)? ‘\n‘:‘ ‘);
77         }
78     }
79     return 0;
80 }