(图画烂的一逼)
按照第一个题例数据来说。从后面开始插,正好能保证它就是在它最后的位置。
f表示的是这个区间还剩余多少个空位。
插入69时候,直接插在最后位置上,那么后面两个位置减去一。
然后更新空位。
大致思路就是这样。
#include <cstdio> #define M 200005 #define mid (l+r)>>1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int f[M<<2],locate[M],num[M],pos[M],n,k,i; void PushPlus(int rt){ f[rt] = f[rt<<1] + f[rt<<1|1]; } void Bulid(int l,int r,int rt){ f[rt] = 0; if(l == r){ f[rt] = 1; return ; } int m = mid ; Bulid(lson); Bulid(rson); PushPlus(rt); } void Query(int p,int l,int r,int rt){ if( l == r ){ f[rt] = 0; k = l; return ; } int m = mid; p<= f[rt<<1]?Query(p,lson):Query(p-f[rt<<1],rson); PushPlus(rt); } int main(){ while(~scanf("%d",&n)){ Bulid(1,n,1); for(i=1;i<=n;i++) scanf("%d %d",&pos[i],&num[i]); for(i=n;i>=1;i--){ Query(pos[i]+1,1,n,1); locate[k] = num[i]; } for(i=1;i<=n;i++){ printf("%d",locate[i]); putchar(i ==n ?'\n':' '); } } return 0; }