有N個人在排隊買票，每個人可站的位置從0到N
後面來的人可能會插隊，也有可能站在當前隊伍的最後面
N行，每行兩個數，pas表示剛來的這個人會站在當前隊伍的第pas位置上
val表示這個人對應的值(0<=val<=i-1)，最後按每個人所在的位置輸出其相應的值
解題思路: 後面加入的人，必定會站在當前隊伍之間或者最後面
因為後面加入的人一定會改變前面確定的順序，所以從後往前來確定隊伍的順序，先看一組數據
0 2
1 1
1 38
0 31
初始化序列為 -1 -1 -1 -1 (-1表示這個位置沒有被確定)
0 31，把值為31的人插入到剩余未確定位置中的第0個位置，得到序列 31 -1 -1 -1
1 38，把值為38的人插入到剩余未確定位置中的第1個位置，得到序列 31 -1 38 -1
以此類推最後的序列為 31 2 38 1
為什麼每次加入的位置剩余空位的第val個呢？
因為我們是從後面往前的，後面加入的數不會影響比它之前的數所在的位置。
用線段樹O(logN)找出左到右的第pas個位置(找出之後再往上更新)，最下層的結點初始化值為1，其余的結點存儲區間值的總和
代碼:
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAX 200100
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1|1)
typedef struct{
int left,right,num;
}Node;
Node Tree[MAX<<2];
int pas[MAX],val[MAX],ans[MAX],kk,n;
void Build(int t,int l,int r)
{
Tree[t].left=l,Tree[t].right=r;
if(Tree[t].left==Tree[t].right)
{
Tree[t].num=1; //初始化為1
return ;
}
int mid=MID(Tree[t].left,Tree[t].right);
Build(L(t),l,mid);
Build(R(t),mid+1,r);
Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}
void Query(int t,int l,int r,int m)
{
if(Tree[t].left==Tree[t].right)
{
kk=Tree[t].left; //找到結點，並且標記
Tree[t].num--;
return ;
}
int mid=MID(Tree[t].left,Tree[t].right);
if(Tree[L(t)].num>=m) //滿足條件時優先選擇左子樹
{
Query(L(t),l,mid,m);
}
else //否則選擇右子樹
{
Query(R(t),mid+1,r,m-Tree[L(t)].num);
}
Tree[t].num=Tree[L(t)].num+Tree[R(t)].num; //更新
}
int main()
{
int i,j,k,m,temp;
while(scanf("%d",&n)!=EOF)
{
memset(Tree,0,sizeof(Tree));
Build(1,1,n);
for(i=1;i<=n;i++)
scanf("%d%d",&pas[i],&val[i]);
for(i=n;i>=1;i--)
{
Query(1,1,n,pas[i]+1); //查找剩余空位中的第pas[i]個位置所在的點
ans[kk]=val[i]; //標記點
}
for(i=1;i<=n;i++)
printf("%d%c",ans[i],i==n?'\n':' ');
}
return 0;
}
