题目链接:http://poj.org/problem?id=2828 题目一看好高深啊 ,不过还好,AC。。 这道题如果正着看,那么每一个人的地方都有可能变动,但是如果倒着看,每一个只要入队了,他的位置就不再改变,这样的话就是一道赤裸裸的线段树单点更新了,每一个结点存储的是该区间内还有多少个空位,每一次遇到一个人的时候,都把他插入到正确的位置,至于怎么算正确的位置,如果当前结点左子树权值大于pos,那么就往左边放,否则就往右边放,放不进去左边的时候,pos要减去左边的空位数,否则的话有可能右边也放不进去,最后根本放不到叶子结点里面。每进入一个区间,该区间的空位数就减少一个,这个千万不要忘了处理。最后用一个数组来存储插入进去以后的最终位置。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|