题解：AT_abc392_f [ABC392F] Insert

ksmgxeh · 2025-02-15 00:49:07 · 题解

赛时看到这道题题面马上想到了另一道很相近的题目：P10497。

因为我们从后往前看，最后一个数的位置一定是确定的，即一定处于 P_n 位置。所以不难想到从后往前进行操作，这样每个数的位置都能被唯一确定。

具体实现也很简单，用树状数组维护每个数前面有多少个位置已经被占用，查询时用二分即能确定当前数的位置。

时间复杂度 O(n\log n)，可以通过。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5+5;
int n,p[N],c[N],a[N];

void add(int x,int k){
    for(int i=x;i<=n;i+=i&-i) c[i]+=k;
}
int get(int x){
    int res=0;
    for(int i=x;i;i-=i&-i) res+=c[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) add(i,1);
    for(int i=n;i>=1;i--){
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(get(mid)>=p[i]) r=mid;
            else l=mid+1;
        } a[l]=i,add(l,-1);
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}