[ABC392F] Insert

· · 题解

前言

这次 ABC 为什么这么水啊。

正文

题目大意就是说给定一个序列 a，依次将 1 到 n 在 A（初始为空）的第 a_i 位插入，问最后的 A 的排列是什么。

首先说一下一个暴力的做法，维护每一个数字 k 出现的下标 p_k。

考虑在每次插入一个数字 x 的时候怎么做。显然，对于所有的 1 \le i < x，需满足 p_i \ge a_i，数字 i 才能往后移动一位。

朴素这么做是 \Theta(n^2) 的，考虑优化。

我们发现需要这么一个数据结构：

  1. 对于区间 [1,i]，所有大于等于 x 的数 +1，
  2. 单点查询 i。

容易发现这个数据结构不好做的，考虑换思路。

正难则反，于是考虑反着来。

不难发现，我们可以先固定 A 中的 n 个位置，然后，依次模拟将数字插入“空位”的过程。

通俗的来说，对于每个数字 i，我们只需找出当前第 a_i 个空闲位置，把 i 放进去即可。

具体而言，我们可以用树状数组实现。为了快速找到第 k 个空位，我们钦定空位为 1，非空位为 0。这样，树状数组维护的前缀和就是单调的，可以使用二分查找。

Code

笨人写的 \Theta(n \log^2 n)，常数较小可以通过，树状数组上二分即可达到 \Theta(n \log n) 的优秀复杂度。

#include <bits/stdc++.h>
#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,m,t,cnt=0;
const int maxn=1e5+10;
const double eps=1e-6;
struct BIT{
    int n;vector<int> brr;
    BIT(int range){n=range;brr.resize(n+1,0);}
    int lowbit(int x){return x&(-x);}
    inline void add(int x, int k){while(x<=n){brr[x]+=k;x+=lowbit(x);}}
    inline int query(int x){int ans=0;while(x!=0){ans+=brr[x];x-=lowbit(x);}return ans;}
    inline int queryRange(int l, int r){return query(r)-query(l-1);}
};
signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n;
    vector<int> a(n+1),ans(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    BIT bit(n);
    for(int i=1;i<=n;i++) bit.add(i,1);
    auto chk=[&](int k){
        int lo=1,hi=n;
        while(lo<hi){
            int mid=(lo+hi)>>1;
            if(bit.query(mid)<k) lo=mid+1;
            else hi=mid;
        }
        return lo;
    };
    for(int i=n;i>=1;i--){
        int pos=chk(a[i]);
        ans[pos]=i;
        bit.add(pos,-1);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}