POJ 2828 -- Buy Tickets 线段树
题目大意：给定n个人进入队伍时的位置，如果某个位置及其后面有人，则后面的人都要向后挪一个位置，这不正是每天都在现实生活中上演的插队问题吗！有n个pos[i]和val[i]，pos[i]表示这个人插入到pos[i]的右面，其实加1的话，更好理解，就是插在什么位置。至于那个val[i]只是为了表示某个人而已，理解成RP什么的都可以
注意到后面的总是可以把前面的覆盖掉，所以考虑总是先确定后面的人的位置，这样题目给出的位置pos就变成了“寻找一个位置，使得这个位置左边的空位置数目为pos”，以第一个样例为例：
把样例倒过来之后是这样的：
2 69
1 33
1 51
0 77
先考虑69号，它的pos是2，说明它插入的时候需要队伍前面有2个人，这样，它就在2号位置上了（从0开始）
再考虑33号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在1号位置上了；
再考虑51号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在3号位置上了；
再考虑77号，它的pos是0，说明它插入的时候需要队伍前面有0个人，这样，它就在0号位置上了。
从最后一个人往前插，这样pos的意义就变成了，前面有多少个空位。线段树上每个节点中存储的是当前时刻，该区间有多少空位
嗯，所以开一个empty数组，结点p表示[l,r]区间内的空位置的数目。
不需要query函数，只需要update函数更新就行。
更新到底是往左子树更新还是右子树更新的原则是：当前需要的空位置数x如果小于[l,mid]区间的空位置数（不包含等于），就往左子树搜(rt<<1)，否则往右子树搜（往右子树搜的时候要注意参数x应该减去左子树的空位置数，也就是变为x-empty[rt<<1]）。（稍微想想应该可以明白的！）
当递归到l==r的时候，说明找到了需要插入的位置，于是将该点的empty减一（要记得Push上来），然后令ans[l]存放插进去的人的val标号。
这个是单点更新，但是这个跟普通的单点更新不一样，普通的单点更新是直接给出了要更新的点的index，但是这个没有直接给出，但是却可以通过empty数组间接求出来。这其实跟树状数组二分tree[]数组找满足条件的点的题目是一样的，这里也是根据empty数组找满足条件（空位置数恰好满足需要）的点，所以可以放在一起考虑一下。
Note: 更新的时候要注意x<empty[mid]的写法是错误的，因为mid仅是index，而不是线段树的标号，应该写成x<empty[rt<<1]。
http://blog.sina.com.cn/s/blog_6635898a0100q16r.html
Read full article from 2828 -- Buy Tickets
Description
Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…
The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.
It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!
People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.
The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.
It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!
People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.
Input
There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi andVali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:
- Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
- Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.
Output
For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.
Sample Input
4 0 77 1 51 1 33 2 69 4 0 20523 1 19243 1 3890 0 31492
Sample Output
77 33 69 51 31492 20523 3890 19243
Hint
The figure below shows how the Little Cat found out the final order of people in the queue described in the first test case of the sample input.
题目大意：给定n个人进入队伍时的位置，如果某个位置及其后面有人，则后面的人都要向后挪一个位置，这不正是每天都在现实生活中上演的插队问题吗！有n个pos[i]和val[i]，pos[i]表示这个人插入到pos[i]的右面，其实加1的话，更好理解，就是插在什么位置。至于那个val[i]只是为了表示某个人而已，理解成RP什么的都可以
是一个逆向思维的运用。
思路：
1 要从后面往前更新线段树
2 线段树记录的是当前区间还剩下多少个记录空间
3 因为后面的插入会使得前面的插入往后退，那么前面插入的下标如果大于前面可以插入的空间，就需要往后退了。
好难理解的操作。仔细观察一下下面update这个函数吧。
二分地去查找适合的插入位置，把插入操作时间效率提高到 O(lgn)，如果使用一般方法插入操作效率就会达到O(n)。
http://shoutmon.com/poj-2828.html注意到后面的总是可以把前面的覆盖掉，所以考虑总是先确定后面的人的位置，这样题目给出的位置pos就变成了“寻找一个位置，使得这个位置左边的空位置数目为pos”，以第一个样例为例：
把样例倒过来之后是这样的：
2 69
1 33
1 51
0 77
先考虑69号，它的pos是2，说明它插入的时候需要队伍前面有2个人，这样，它就在2号位置上了（从0开始）
再考虑33号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在1号位置上了；
再考虑51号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在3号位置上了；
再考虑77号，它的pos是0，说明它插入的时候需要队伍前面有0个人，这样，它就在0号位置上了。
从最后一个人往前插，这样pos的意义就变成了，前面有多少个空位。线段树上每个节点中存储的是当前时刻，该区间有多少空位
嗯，所以开一个empty数组，结点p表示[l,r]区间内的空位置的数目。
不需要query函数，只需要update函数更新就行。
更新到底是往左子树更新还是右子树更新的原则是：当前需要的空位置数x如果小于[l,mid]区间的空位置数（不包含等于），就往左子树搜(rt<<1)，否则往右子树搜（往右子树搜的时候要注意参数x应该减去左子树的空位置数，也就是变为x-empty[rt<<1]）。（稍微想想应该可以明白的！）
当递归到l==r的时候，说明找到了需要插入的位置，于是将该点的empty减一（要记得Push上来），然后令ans[l]存放插进去的人的val标号。
这个是单点更新，但是这个跟普通的单点更新不一样，普通的单点更新是直接给出了要更新的点的index，但是这个没有直接给出，但是却可以通过empty数组间接求出来。这其实跟树状数组二分tree[]数组找满足条件的点的题目是一样的，这里也是根据empty数组找满足条件（空位置数恰好满足需要）的点，所以可以放在一起考虑一下。
Note: 更新的时候要注意x<empty[mid]的写法是错误的，因为mid仅是index，而不是线段树的标号，应该写成x<empty[rt<<1]。
http://blog.sina.com.cn/s/blog_6635898a0100q16r.html
struct{
}node[3*MAX];
int id, pos[MAX], val[MAX], ans[MAX];
}node[3*MAX];
int id, pos[MAX], val[MAX], ans[MAX];
void BuildTree(int left, int right, int u){
}
}
void updata(int pos, int u){
}
}
int main(){
}
http://www.cnblogs.com/rayn1027/p/3731925.html}
12 int pos[MAX], val[MAX], ans[MAX]; 13 int tree[MAX*3], index; 14 15 void Build(int k, int l, int r) 16 { 17 tree[k] = r - l + 1; //开始时每个节点都有空位 18 if(l == r) 19 return ; 20 int mid = (l + r) >> 1; 21 Build(k<<1, l, mid); 22 Build(k<<1|1, mid+1, r); 23 } 24 void Update(int k, int l, int r, int pos) 25 { 26 tree[k]--; //单点更新，减少一个空位 27 if(l == r) 28 { 29 index = l; 30 return ; 31 } 32 int mid = (l + r) >> 1; 33 if(tree[k<<1] >= pos) //如果当前位置的左边空位够的话就落在左边 34 { 35 Update(k<<1, l, mid, pos); 36 } 37 else 38 { 39 pos -= tree[k<<1]; //否则，就把左边的空位减去，再在右边定位 40 Update(k<<1|1, mid+1, r, pos); 41 } 42 } 43 int main() 44 { 45 #ifdef _Rayn 46 freopen("in.txt", "r",stdin); 47 #endif 48 int n; 49 while(scanf("%d", &n) != EOF) 50 { 51 Build(1, 1, n); 52 for(int i=1; i<=n; ++i) 53 { 54 scanf("%d%d", &pos[i], &val[i]); 55 } 56 for(int i=n; i>=1; --i) 57 { 58 Update(1, 1, n, pos[i]+1); 59 ans[index] = val[i]; 60 } 61 for(int i=1; i<=n; ++i) 62 { 63 printf("%d%c", ans[i], (i == n)? '\n':' '); 64 } 65 } 66 return 0; 67 }Also check http://www.cnblogs.com/rayn1027/p/3731925.html
Read full article from 2828 -- Buy Tickets
