题解：AT_abc392_f [ABC392F] Insert

· · 题解

atcoder题目传送门

洛谷题目传送门

题目描述

有一个空数组 A。对于 i=1,2,\dots,N，依次进行以下操作：

完成所有操作后，输出最终数组 A。

题目大意

我们有一个空数组 A，然后依次进行 N 次操作。对于第 i 次操作（i 从 1 到 N），我们将数字 i 插入到数组 A 中，使其成为数组 A 的第 P_i 个元素。最终，我们需要输出完成所有操作后的数组 A。

思路

我们可以模拟插入操作，但 N 的最大值是 5×10^5，直接数组模拟插入操作会时间复杂度过高（每次插入操作的时间复杂度为 O(N)，总时间复杂度为 O(N^2)），肯定超时。

因此，我们需要一种更高效的数据结构来支持快速插入操作。这里可以使用线段树来维护数组的空位信息。线段树可以在 O(log N) 的时间内完成插入操作，从而将总时间复杂度降低到 O(N log N)。

线段树的构建

线段树的每个节点维护一个区间内的空位数量。初始时，整个数组都是空的，因此根节点的空位数量为 N。每次插入一个数字时，我们需要找到第 P_i 个空位，并将数字插入到该位置。插入后，该位置的空位数量减少 1。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,p[500001],ans[500001],tmp[2000001];
// ans 存储最终的数组
// tmp 线段树的节点数组，用于维护每个区间的空位数量
// 线段树的插入操作
// 通过递归的方式找到第 w 个空位，并将数字 u 插入到该位置
void add(int l,int r,int o,int u,int v,int w){
    // l r 当前节点表示的区间范围,例如, l=1 , r=n 表示当前节点代表整个数组的范围
    // o 当前节点的索引,线段树中,节点的索引从 1 开始,左子节点的索引为 o<<1 ,右子节点的索引为 (o<<1)+1
    // u 要插入的数字,例如, u=i 表示插入数字 i
    // v 表示在当前区间 [l,r] 之前的所有区间中,已经有多少个空位被占用了,这个参数用于计算目标位置 w 在当前区间中的相对位置
    // w 目标插入位置,表示我们需要找到第 w 个空位来插入数字 u
    tmp[o]++;// 当前节点的空位数量减 1
    if(l==r){
        ans[l]=u;// 找到目标位置，插入数字 u
        return;
    }
    // 判断目标位置在左子树还是右子树
    // ((l+r)>>1)-l+1 表示左子树的区间长度
    // tmp[o<<1] 左子树中已经被占用的空位数量
    // v+((l+r)>>1)-l+1-tmp[o<<1] 表示左子树中剩余的空位数量
    // 如果剩余的空位数量大于等于 w，说明目标位置在左子树中,参数 v 和 w 保持不变
    if(v+((l+r)>>1)-l+1-tmp[o<<1]>=w)add(l,(l+r)>>1,o<<1,u,v,w);// 目标位置在左子树
    // l 和 (l+r)>>1 表示左子树的区间范围 [l,mid] ,其中 mid=(l+r)>>1
    // o<<1 左子节点在线段树中的索引
    // u 要插入的数字，保持不变
    // v 由于我们进入左子树，v 的值保持不变
    // w 目标插入位置，保持不变
    else add(((l+r)>>1)+1,r,(o<<1)+1,u,v+((l+r)>>1)-l+1-tmp[o<<1],w);// 目标位置在右子树,如果目标位置不在左子树中,则一定在右子树中,参数 v 需要更新，加上左子树的区间长度并减去左子树中已经被占用的空位数量
    // ((l+r)>>1)+1 和 r 表示右子树的区间范围 [mid+1,r] ,其中 mid=(l+r)>>1
    // (o<<1)+1 右子节点在线段树中的索引
    // u 要插入的数字，保持不变
    // v+((l+r)>>1)-l+1-tmp[o<<1] 表示在右子树之前的所有区间中,已经有多少个空位被占用了,这里需要加上左子树的区间长度 ((l+r)>>1)-l+1 , 并减去左子树中已经被占用的空位数量 tmp[o<<1]
    // w 目标插入位置，保持不变
}
signed main(){
    cin >> n;
    for(int i=1;i<=n;i++)cin >> p[i];
    for(int i=n;i>=1;i--)add(1,n,1,i,0,p[i]);// 从后往前插入
    for(int i=1;i<=n;i++)cout << ans[i] << " ";// 输出最终数组
    return 0;
}