pku2828 Buy Tickets

http://poj.org/problem?id=2828

线段树，单点更新

反向添加，每次放到第a[i]个空位上，用线段树维护区间内空位数，

单点查询，查询第x个空位的下标；

 1 #include <stdio.h>
 2 
 3 #define lson l, m, root<<1
 4 #define rson m+1, r, root<<1|1
 5 
 6 const int maxn = 200010;
 7 int sum[maxn<<2];
 8 
 9 void push_up(int root)
10 {
11     sum[root] = sum[root<<1] + sum[root<<1|1];
12 }
13 
14 void build(int l, int r, int root)
15 {
16     int m;
17     if(l == r)
18     {
19         sum[root] = 1;
20         return;
21     }
22     m = (l + r) >> 1;
23     build(lson);
24     build(rson);
25     push_up(root);
26 }
27 
28 void update(int x, int l, int r, int root)
29 {
30     int m;
31     if(l == r)
32     {
33         sum[root] = 0;
34         return;
35     }
36     m = (l + r) >> 1;
37     if(x <= m)
38     {
39         update(x, lson);
40     }
41     if(m+1 <= x)
42     {
43         update(x, rson);
44     }
45     push_up(root);
46 }
47 
48 int query(int x, int l, int r, int root)
49 {
50     int m;
51     if(l == r)
52     {
53         return l;
54     }
55     m = (l + r) >> 1;
56     if(x <= sum[root<<1])
57     {
58         return query(x, lson);
59     }
60     return query(x-sum[root<<1], rson);
61 }
62 
63 int main()
64 {
65     int i, n, a[maxn], b[maxn], result[maxn], temp;
66     while(~scanf("%d", &n))
67     {
68         for(i=1; i<=n; i++)
69         {
70             scanf("%d%d", a+i, b+i);
71             a[i] ++;
72         }
73         build(1, n, 1);
74         for(i=n; i>=1; i--)
75         {
76             temp = query(a[i], 1, n, 1);
77             result[temp] = i;
78             update(temp, 1, n, 1);
79         }
80         for(i=1; i<=n; i++)
81         {
82             printf(i-n? "%d ": "%d\n", b[result[i]]);
83         }
84     }
85     return 0;
86 }