題目鏈接：http://poj.org/problem?id=2828 題目一看好高深啊 ，不過還好，AC。。 這道題如果正著看，那么每一個人的地方都有可能變動，但是如果倒著看，每一個只要入隊了，他的位置就不再改變，這樣的話就是一道赤裸裸的線段樹單點更新了，每一個結點存儲的是該區間內還有多少個空位，每一次遇到一個人的時候，都把他插入到正確的位置，至于怎么算正確的位置，如果當前結點左子樹權值大于pos，那么就往左邊放，否則就往右邊放，放不進去左邊的時候，pos要減去左邊的空位數，否則的話有可能右邊也放不進去，最后根本放不到葉子結點里面。每進入一個區間，該區間的空位數就減少一個，這個千萬不要忘了處理。最后用一個數組來存儲插入進去以后的最終位置。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 200010;
11 int sum[maxn << 2], pos[maxn], val[maxn], ans[maxn], id;
12 void PushUp(int rt)
13 {
14 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
15 }
16 void build(int l, int r, int rt)
17 {
18 if (l == r)
19 {
20 sum[rt] = 1;
21 return;
22 }
23 int m = (l + r) >> 1;
24 build(lson);
25 build(rson);
26 PushUp(rt);
27 }
28 void query(int p, int l, int r, int rt)
29 {
30 sum[rt]--;
31 if (l == r)
32 {
33 id = l;
34 return;
35 }
36 int m = (l + r) >> 1;
37 if (p <= sum[rt << 1]) query(p, lson);
38 else
39 {
40 p -= sum[rt << 1];
41 query(p, rson);
42 }
43 }
44 int main()
45 {
46 int n;
47 while (scanf("%d", &n) != EOF)
48 {
49 build(1, n, 1);
50 for (int i = 1; i <= n; i++) scanf("%d%d", &pos[i], &val[i]);
51 for (int i = n; i >= 1; i--)
52 {
53 query(pos[i] + 1, 1, n, 1);
54 ans[id] = val[i];
55 }
56 for (int i = 1; i <= n; i++)
57 {
58 printf("%d", ans[i]);
59 if (i == n) printf("\n");
60 else printf(" ");
61 }
62 }
63 return 0;
64
|