POJ-2828

有 $N$ 个人排队，每一个人都有一个 $val$ 来对应，每一个后来人都会插入当前队伍的某一个位置 $pos$ 。要求把队伍最后的状态输出。

思路

刚读完题以为是链表，然后思考了一会儿发现不容易动态变更各个位置的人。

然后想到了倒序处理，很容易发现最后一个插队的人的位置 $pos_n$ 一定是 $pos_n+1$ 。

于是这样的话，对第 $i$ 个人插入的位置 $pos_i$ ，只需将其放到第 $pos_i +1$ 个空位即可。

所以考虑用线段树维护区间和，然后查询序列 $k$ 大值即可。

代码

#include<bits/stdc++.h>
#define N 200010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,ans[N],pos[N],val[N];
class Segment_Tree{
  private:
    int sum[N<<2];
    #define s(x) sum[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            s(p)=1;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int x) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)=0;
            return ;
        }
        modify(ls,l,mid,x),modify(rs,mid+1,r,x);
        update(p);
    }
    int ask(int p,int l,int r,int x) {
        if(l==r) return l;
        if(s(ls)>=x) return ask(ls,l,mid,x);
        if(s(ls)<x) return ask(rs,mid+1,r,x-s(ls));
    }
}SMT;

void init() {
    memset(ans,0,sizeof(ans));
    memset(val,0,sizeof(val));
    memset(pos,0,sizeof(pos));
    SMT.build(1,1,n);
}

int main() {
    while(cin>>n) {
        init();
        for(int i=1;i<=n;i++) pos[i]=read()+1,val[i]=read();
        for(int i=n;i>=1;i--) {
            int t=SMT.ask(1,1,n,pos[i]);
            ans[t]=val[i];
            SMT.modify(1,1,n,t);
        }
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        printf("\n");
    }

    return 0;
}