[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,i]$ ，所有大于等于 $x$ 的数 $+1$ ，
单点查询 $i$ 。

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

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

不难发现，我们可以先固定

A

中的

n

个位置，然后，依次模拟将数字插入“空位”的过程。

通俗的来说，对于每个数字

i

，我们只需找出当前第

a_i

个空闲位置，把

i

放进去即可。

具体而言，我们可以用树状数组实现。为了快速找到第

k

个空位，我们钦定空位为

1

，非空位为

0

。这样，树状数组维护的前缀和就是单调的，可以使用二分查找。

Code

笨人写的

\Theta(n \log^2 n)

，常数较小可以通过，树状数组上二分即可达到

\Theta(n \log n)

的优秀复杂度。

CPP

#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;
}

文章操作

前言

正文

Code

相关推荐

评论

[ABC392F] Insert