題意：
給出一個N，接下來是N個數，每個數有一個插入的位置。
輸出最後的順序。
思路：
一開始以為就是鏈表插入，然後看了下數據量。就沒想法了。
就用了線段樹，建樹和詢問都是很基礎的東西，就是最後處理位置有一些技巧。
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 200005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;
int n;
struct kdq
{
int l, r;
int num;
} tree[Max*4];
int pos[Max],num[Max];
int newpos[Max];//記錄插入後的新地址
void build_tree(int l,int r,int u)
{
tree[u].l=l;
tree[u].r=r;
tree[u].num=r-l+1;
if(l==r)return ;
int mid=(l+r)>>1;
build_tree(l,mid,LL(u));
build_tree(mid+1,r,RR(u));
}
int query(int id,int u)
{
tree[u].num--;//每次插入，則區間值遞減
if(tree[u].l==tree[u].r)
return tree[u].l;
if(tree[LL(u)].num>=id)//盡量往左邊插入
return query(id,LL(u));
else
return query(id-tree[LL(u)].num,RR(u));
}
int main()
{
int i,j,k,l,m;
while(~scanf("%d",&n))
{
for(i=1; i<=n; i++)
{
scanf("%d%d",&pos[i],&num[i]);
pos[i]++;
}
build_tree(1,n,1);
for(i=n; i>=1; i--)
newpos[query(pos[i],1)]=i;//反向插入。假設pos[n]和pos[n-1]相等，那麼第n個數肯定在第n-1個數之前，因為後插入。
//所以這裡直接從n到1進行插入，一遍插入結束之後就是新的位置，如果從前往後插入，還得考慮相同的位置進行移位
for(i=1; i<=n; i++)
printf("%d ",num[newpos[i]]);//最後直接輸出各自的新位置
printf("\n");
}
return 0;
}
