POJ 2828 线段树

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 using namespace std;
 5 #define maxn 200010
 6 
 7 int seq[maxn];
 8 int spare[maxn<<2];
 9 
10 void pushUp(int rt) {
11    spare[rt] = spare[rt<<1] + spare[rt<<1|1];
12 }
13 
14 void create(int rt, int l, int r) {
15    if (l == r) {
16        spare[rt] = 1;
17        return;
18    }
19    int mid = (l+r)>>1;
20    create(rt<<1, l, mid);
21    create(rt<<1|1, mid+1, r);
22    pushUp(rt);
23 }
24 
25 void update(int p, int v, int l, int r, int rt) {
26     if (l == r) {
27       seq[l] = v;
28       spare[rt] = 0;
29       return;
30     }
31 
32     int mid = (l+r)>>1;
33     if (spare[rt<<1] >= p) update(p, v, l, mid, rt<<1);
34     else update(p-spare[rt<<1], v, mid+1, r, rt<<1|1);
35     pushUp(rt);
36 }
37 
38 int main() {
39     int n;
40     int pos[maxn], val[maxn];
41     while(scanf("%d", &n) != EOF) {
42        create(1, 1, n);
43        int i;
44        for (i=1; i<=n; ++i) {
45           scanf("%d%d", &pos[i], &val[i]);
46        }
47 
48        for (i=n; i>=1; --i) {
49          update(pos[i]+1, val[i], 1, n, 1);
50        }
51        for (i=1; i<=n; ++i) {
52           if (i != 1) printf(" ");
53           printf("%d", seq[i]);
54        }
55        printf("\n");
56     }
57     return 0;
58 }