?

题意：有个家伙春节买票，闲的没事想了一个让我们做= =！，是酱紫的，有n个人，编号是val，将插队，其序号变为pos，编号的范围[0,n)。

刚开始真心没有看出来是个线段树题，要不是在做线段树专题，打死我也不会向线段树上靠拢。

想想这是用线段树解决一个什么样的模型呢？

1：每个人有固定的位置，虽然中途在不停加入，但到最后，一个萝卜一个坑

2：是不停加入成员，而不是改变

3：用线段树记录空余位置

?

没想到用线段树是我遇到的第一个问题，第二个便是建树。一般情况下，都是1-n建树，而这个题，最好是0-n-1建树，很方便。其实刚开始没有大胆尝试是因为没有意识到线段树的每个节点的l、r和rt是没有什么必然关系的，l、r控制着左右端点，而rt只不过是一个下标罢了，仅仅是表示保存在了数组哪个位置。其相对独立。还有便是线段树节点的含义，每个子叶表示一个位置，其父节点存储了可用的位置数，每加入一个成员，便占用一个位置，而节点的编号便是这个成员的最终位置。对于建树的最后一个问题，怎么把每个人加入到树中？因为对于这个题，最后一个插队的，其编号绝对是他最终的位置编号，那么，我们就可以倒序建树。

最后一个问题，在update的时候，怎么决定向左向右深入，上面已经说倒序建树，那么，当在建树的时候，如果左枝剩余的人数少于他的pos（编号），那么就认为左枝的位置放不下他，然后就可以向右枝深入。

?

代码：

?

#include 
  
   
#include 
   
     #define LS rt << 1 #define RS rt << 1 | 1 #define LSON l,m,LS #define RSON m + 1,r,RS #define MID (l + r) >> 1 #define ROOT 0,n - 1,1 #define MAX 200010 using namespace std; int pri[MAX]; int cnt[MAX << 2]; int pos[MAX],val[MAX]; inline void pushup(int rt) { cnt[rt] = cnt[LS] + cnt[RS]; } void build(int l,int r,int rt) { if(l == r) { cnt[rt] = 1; return ; } int m = MID; build(LSON); build(RSON); pushup(rt); } void update(int pos,int val,int l,int r,int rt) { if(l == r) { cnt[rt] = 0; pri[l] = val; return ; } int m = MID; if(cnt[LS] > pos) update(pos,val,LSON); else update(pos - cnt[LS],val,RSON); pushup(rt); } int main() { int n; while(~scanf(%d,&n)) { build(ROOT); for(int i = 0;i < n;i++) scanf(%d%d,&pos[i],&val[i]); for(int i = n - 1;i >= 0;i--) update(pos[i],val[i],ROOT); for(int i = 0;i < n;i++) printf(%d%c,pri[i],i < n - 1 ? ' ' : ' '); } return 0; } 
   
  

?