一道并不是太难的线段树练习题。
题意大概是将一些数字插入一个序列中，每当插到一个位置之后，会把当前以及后面的数字都往后移一格，最后输出他们的顺序。由于每次插入都会影响到其他数字的位置，因此越靠后的插入，自身的位置越不容易被影响——而最后一个数插到哪，最终位置就是哪。因此最好的办法就是从后往前推。 假设一共有n个人，对于倒数第i个人而言，如果他要插在第k个位置上，那么只需要从前往后数到第k个空位，然后把它插入就可以了；后面已经处理过的i-1个人的插入对于他而言没有影响。线段树的random域就可以用来保存该段区间的空位数。所以问题变成，找到第 i 个空位，线段树记录该区间里有几个空位。
具体代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
typedef long long ll;
const int maxn = 200010;
int n;
int sum[4*maxn+10];//以数组形式建立线段树，存储空位数
int pos[maxn+1], val[maxn+1];
int ans[maxn+1];//存储答案
void pushUp(int root) {
sum[root] = sum[root<<1] + sum[root<<1|1];
return;
}
void build(int root, int l, int r) {//建树
if(l == r) {
sum[root] = 1;
return;
}
else {
int m = (l+r) >> 1;
build(root<<1, l, m);
build(root<<1|1, m+1, r);
pushUp(root);
return;
}
}
int query(int root, int l, int r, int pos) {
if(l == r) {//找到空位，把这个位占用
sum[root] = 0;
return l;
}
else {
int m = (l+r) >> 1;
int rank;//空位
if(sum[root<<1] > pos)//在左子树中找空位
rank = query(root<<1, l, m, pos);
else
rank = query(root<<1|1, m+1, r, pos-sum[root<<1]);
pushUp(root);
return rank;
}
}
int main() {
while(~scanf("%d", &n)) {
for(int i = 1;i <= n;i++)
scanf("%d %d", &pos[i], &val[i]);
build(1, 0, n-1);
for(int i = n;i > 0;i--) {
int res = query(1, 0, n-1, pos[i]);//查找插入的空位
ans[res] = val[i];//将相应权值存入所查到的下标对应的ans数组中
}
for(int i = 0;i < n-1;i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n-1]);
}
return 0;
}
