题解：P10688 Buy Tickets

HPXXZYY · 2025-09-01 21:33:40 · 题解

这是一道好题。

考虑 p_{i} 表示第 i 个来的人最终排在哪一个位置。

第 i 个人会排在第 \text{pos}_{i} 个人的后面，于是后面的人的 p 都会加一。但是下标并不连续，因此无法用线段树或树状数组维护。

正面思考遇到困难。

很巧妙的正难则反。我们先考虑第 n 个来插队的人最终排在了哪里。

显然他就排在 (\text{pos}_{n}+1) 这个位置。

为什么是这个位置？因为这个位置前面有 \text{pos}_{n} 个空位。

于是第 i 个人插队时，问题转化为哪一个位置前面恰好有 \text{pos}_{i} 个空位。

可以二分配套树状数组求解。

const int N=2e5+100;

class Fenwick_Tree{
    public:
        void modify(int pos,int val){
            for(int i=pos;i<=n;i+=lowbit(i))
                c[i]+=val;
        }
        int query(int pos){
            int res=0;
            for(int i=pos;i;i-=lowbit(i))
                res+=c[i];
            return res;
        }

        void init(int n=0){
            this->n=n;
            for(int i=1;i<=n;i++)
                c[i]=0;
        }
    private:
        int c[N],n;

        int lowbit(int x){
            return x&(-x);
        }
};

Fenwick_Tree ft;

int pos[N],rec[N],val[N],n;

int Bineary_Search(int pos){
    int l=1,r=n,res=1;
    while (l<=r){
        int mid=(l+r)>>1;

        if (ft.query(mid-1)<=pos){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }

    return res;
}

int main(){
    while (~scanf("%d",&n)){
        ft.init(n);

        for(int i=1;i<=n;i++){
            pos[i]=read();
            val[i]=read();
        }

        for(int i=1;i<=n;i++)
            ft.modify(i,1);

        for(int i=n;i>=1;i--){
            int p=Bineary_Search(pos[i]);

            ft.modify(p,-1);
            rec[p]=i;
        }

        for(int i=1;i<=n;i++)
            printf("%d%c",val[rec[i]],(i==n?'\n':' '));
    }

    return 0;
}