POJ 2828 Buy Tickets

待编辑
需一步思路转化
 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 
10 int pos[MAXN], val[MAXN];
11 int sum[MAXN << 2];
12 int ans[MAXN];
13 int N, id;
14 
15 void build( int l, int r, int rt )
16 {
17     sum[rt] = r - l + 1;
18     if ( l == r ) return;
19 
20     int m = ( l + r ) >> 1;
21     build( lson );
22     build( rson );
23     return;
24 }
25 
26 void Update( int po, int l, int r, int rt )
27 {
28     --sum[rt];
29     if ( l == r )
30     {
31         id = l;
32         return;
33     }
34 
35     int m = ( l + r ) >> 1;
36 
37     if ( po <= sum[rt << 1] ) Update( po, lson );
38     else Update( po - sum[rt << 1], rson );
39 
40     return;
41 }
42 
43 int main()
44 {
45     while ( ~scanf( "%d", &N ) )
46     {
47         build( 1, N, 1 );
48         for ( int i = 1; i <= N; ++i )
49             scanf( "%d%d", &pos[i], &val[i] );
50 
51         for ( int i = N; i > 0; --i )
52         {
53             Update( pos[i] + 1, 1, N, 1 );
54             ans[id] = val[i];
55         }
56         printf( "%d", ans[1] );
57         for ( int i = 2; i <= N; ++i )
58             printf( " %d", ans[i] );
59         puts("");
60     }
61     return 0;
62 }