Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1)
现在问最后的序列，从1到n输出n个人的rp值
思路：第二道线段树，并不会做，看了题解。
比较关键的一点是：按照顺序的话，当后来的一个人插入到前面，那么之前很多人排好的位置将发生改变，这个代价是巨大的。
由于越后来的人越容易确定位置，因此正确的做法是倒序处理。
对于第i个人，我们把他放在从前往后数的第i个空的位置即可。
接下来需要做的就是线段树处理，线段树存储的信息是某一个区间中空位置的个数。
感觉是一道很好的题目，对于新手来说并不是很容易，不过理解了这道题目以后，感觉进一步理解线段树，有点开心。
代码实现
1/*************************************************************************
2 > File Name: code/poj/2828.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年10月29日 星期四 09时00分08秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#include<cctype>
20#define yn hez111qqz
21#define j1 cute111qqz
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=2E5+7;
32int pos[N],val[N];
33int n;
34int tree[N<<2]; //tree[i]存储的是以i为根节点的子树对应的区间中空位置的数量。
35int ans[N];
36void PushUp(int rt)
37{
38 tree[rt] = tree[rt<<1]+tree[rt<<1|1]; //一段区间空位置的数量等于两端子区间中空位置的数量的和。
39}
40void build(int l,int r,int rt)
41{
42 if (l==r)
43 {
44 tree[rt] = 1; //初始的空位置的数量为区间长度r-l+1
45 return ;
46 }
47 int m = (l+r)>>1;
48 build(lson);
49 build(rson);
50 PushUp(rt);
51}
52void update (int p,int val,int l,int r,int rt)
53{
54 if (l==r) //终于找到了该点的归属。。。
55 {
56 ans[l] = val;
57 tree[rt]--;
58 return ;
59 }
60 int m = (l+r)>>1;
61 if (p<=tree[rt<<1]) update(p,val,lson); //如果左子树所代表的区间中空位置的数目够的话就放左边
62 else update(p-tree[rt<<1],val,rson);//否则放右边，一共需要p个空位置，左边提供了tree[rt<<1]个，还需要右边提供p-tree[rt<<1]个。
63 PushUp(rt);
64}
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70 while (~scanf("%d",&n))
71 {
72 for ( int i = 0 ; i < n ;i++) scanf("%d %d",&pos[i],&val[i]);
73 build(1,n,1);
74 for ( int i = n-1 ; i >= 0 ; i--)
75 {
76 pos[i]++;
77 update(pos[i],val[i],1,n,1);
78 }
79 for ( int i = 1 ; i <= n-1 ; i++) printf("%d ",ans[i]);
80 printf("%d\n",ans[n]);
81 }
82 #ifndef ONLINE_JUDGE
83 fclose(stdin);
84 #endif
85 return 0;
86}