题解：AT_abc392_f [ABC392F] Insert

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