F - Insert
Source: atcoder
Difficulty: 500

Problem Statement
There is an empty array
A
. For
i = 1,2,\ldots,N
, perform the following operation in order:
Insert the number
i
into
A
so that it becomes the
P_i
-th element from the beginning.
More precisely, replace
A
with the concatenation of the first
P_i-1
elements of
A
, then
i
, then the remaining elements of
A
starting from the
P_i
-th element, in this order.
Output the final array
A
after all operations have been completed.
Constraints
1 \leq N \leq 5\times 10^5
1 \leq P_i \leq i
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
P_1
P_2
\ldots
P_N
Output
Let the final array be
A = (A_1, A_2, \ldots, A_N)
.
Print
A_1, A_2, \ldots, A_N
in this order, separated by spaces.
Sample Input 1
4
1 1 2 1
Sample Output 1
4 2 3 1
The operations are performed as follows:
Insert the number
1
so that it becomes the 1st element of
A
. Now,
A = (1)
.
Insert the number
2
so that it becomes the 1st element of
A
. Now,
A = (2, 1)
.
Insert the number
3
so that it becomes the 2nd element of
A
. Now,
A = (2, 3, 1)
.
Insert the number
4
so that it becomes the 1st element of
A
. Now,
A = (4, 2, 3, 1)
.
Sample Input 2
5
1 2 3 4 5
Sample Output 2
1 2 3 4 5

C++ solution:
#include<bits/stdc++.h>
using i64=long long;
using u64=unsigned long long;
typedef std::pair<int,int> PII;

const int mod=1e9+7;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};


void solve(){
    int n;
    std::cin>>n;
    Fenwick<int> fen(n);
    for(int i=0;i<n;i++){
        fen.add(i,1);
    }
    std::vector<int> a(n);
    for(int i=0;i<n;i++){
        std::cin>>a[i];
        a[i]--;
    }
    std::vector<int> b(n);
    for(int i=n-1;i>=0;i--){
        int x=fen.select(a[i]);
        b[x]=i;
        fen.add(x,-1);
    }
    for(int i=0;i<n;i++){
        std::cout<<b[i]+1<<' ';
    }
    std::cout<<'\n';
}

int main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int tt=1;
    //std::cin>>tt;//多组输入
    while(tt--){
        solve();
    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"math/bits"
	"os"
	"unsafe"
)

// https://atcoder.jp/contests/abc392/tasks/abc392_f
func main() {
	const eof = 0
	in := os.Stdin
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12)

	rc := func() byte {
		if _i == _n {
			_n, _ = in.Read(buf)
			if _n == 0 {
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	NextInt := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}
	_ = NextInt

	n := int32(NextInt())
	sqrt := int32(math.Sqrt(float64(n))) + 1
	arr := NewSqrtArray(0, func(i int32) int32 { return 0 }, sqrt)

	for i := int32(0); i < n; i++ {
		pos := int32(NextInt())
		pos--
		arr.Insert(pos, i+1)
	}

	arr.ForEach(func(_ int32, v int32) bool {
		fmt.Fprint(out, v, " ")
		return false
	})
}

type E = int32

// 使用分块+树状数组维护的动态数组.
type SqrtArray struct {
	n                 int32
	blockSize         int32
	threshold         int32
	shouldRebuildTree bool
	blocks            [][]E
	tree              []int32 // 每个块块长的前缀和
}

func NewSqrtArray(n int32, f func(i int32) E, blockSize int32) *SqrtArray {
	if blockSize < 1 {
		blockSize = int32(math.Sqrt(float64(n))) + 1
	}

	res := &SqrtArray{n: n, blockSize: blockSize, threshold: blockSize << 1, shouldRebuildTree: true}
	blockCount := (n + blockSize - 1) / blockSize
	blocks := make([][]E, blockCount)
	for bid := int32(0); bid < blockCount; bid++ {
		start, end := bid*blockSize, (bid+1)*blockSize
		if end > n {
			end = n
		}
		bucket := make([]E, end-start)
		for i := start; i < end; i++ {
			bucket[i-start] = f(i)
		}
		blocks[bid] = bucket
	}
	res.blocks = blocks
	return res
}

func (sl *SqrtArray) Insert(index int32, value E) {
	if len(sl.blocks) == 0 {
		sl.blocks = append(sl.blocks, []E{value})
		sl.shouldRebuildTree = true
		sl.n++
		return
	}

	if index < 0 {
		index += sl.n
	}
	if index < 0 {
		index = 0
	}
	if index > sl.n {
		index = sl.n
	}

	pos, startIndex := sl._findKth(index)
	sl._updateTree(pos, true)
	sl.blocks[pos] = Insert(sl.blocks[pos], int(startIndex), value)

	// n -> load + (n - load)
	if n := int32(len(sl.blocks[pos])); n > sl.threshold {
		left, right := Clone(sl.blocks[pos][:sl.blockSize]), sl.blocks[pos][sl.blockSize:]
		sl.blocks = Replace(sl.blocks, int(pos), int(pos+1), left, right)
		sl.shouldRebuildTree = true
	}

	sl.n++
	return
}

func (sl *SqrtArray) Pop(index int32) E {
	if index < 0 {
		index += sl.n
	}
	pos, startIndex := sl._findKth(index)
	value := sl.blocks[pos][startIndex]
	// !delete element
	sl.n--
	sl._updateTree(pos, false)
	sl.blocks[pos] = Replace(sl.blocks[pos], int(startIndex), int(startIndex+1))

	if len(sl.blocks[pos]) == 0 {
		// !delete block
		sl.blocks = Replace(sl.blocks, int(pos), int(pos+1))
		sl.shouldRebuildTree = true
	}
	return value
}

func (sl *SqrtArray) Get(index int32) E {
	if index < 0 {
		index += sl.n
	}
	pos, startIndex := sl._findKth(index)
	return sl.blocks[pos][startIndex]
}

func (sl *SqrtArray) Set(index int32, value E) {
	if index < 0 {
		index += sl.n
	}
	pos, startIndex := sl._findKth(index)
	oldValue := sl.blocks[pos][startIndex]
	if oldValue == value {
		return
	}
	sl.blocks[pos][startIndex] = value
}

func (sl *SqrtArray) Len() int32 {
	return sl.n
}

func (sl *SqrtArray) Clear() {
	sl.n = 0
	sl.shouldRebuildTree = true
	sl.blocks = sl.blocks[:0]
	sl.tree = sl.tree[:0]
}

func (sl *SqrtArray) GetAll() []E {
	res := make([]E, 0, sl.n)
	for _, block := range sl.blocks {
		res = append(res, block...)
	}
	return res
}

func (sl *SqrtArray) ForEach(f func(i int32, v E) (shouldBreak bool)) {
	ptr := int32(0)
	for _, block := range sl.blocks {
		for _, v := range block {
			if f(ptr, v) {
				return
			}
			ptr++
		}
	}
}

func (sl *SqrtArray) _rebuildTree() {
	sl.tree = make([]int32, len(sl.blocks))
	for i := 0; i < len(sl.blocks); i++ {
		sl.tree[i] = int32(len(sl.blocks[i]))
	}
	tree := sl.tree
	m := int32(len(tree))
	for i := int32(0); i < m; i++ {
		j := i | (i + 1)
		if j < m {
			tree[j] += tree[i]
		}
	}
	sl.shouldRebuildTree = false
}

func (sl *SqrtArray) _updateTree(index int32, addOne bool) {
	if sl.shouldRebuildTree {
		return
	}
	tree := sl.tree
	m := int32(len(tree))
	if addOne {
		for i := index; i < m; i |= i + 1 {
			tree[i]++
		}
	} else {
		for i := index; i < m; i |= i + 1 {
			tree[i]--
		}
	}
}

func (sl *SqrtArray) _findKth(k int32) (pos, index int32) {
	if k < int32(len(sl.blocks[0])) {
		return 0, k
	}
	last := int32(len(sl.blocks) - 1)
	lastLen := int32(len(sl.blocks[last]))
	if k >= sl.n {
		return last, lastLen
	}
	if k >= sl.n-lastLen {
		return last, k + lastLen - sl.n
	}
	if sl.shouldRebuildTree {
		sl._rebuildTree()
	}
	tree := sl.tree
	pos = -1
	m := int32(len(tree))
	bitLen := int8(bits.Len32(uint32(m)))
	for d := bitLen - 1; d >= 0; d-- {
		next := pos + (1 << d)
		if next < m && k >= tree[next] {
			pos = next
			k -= tree[pos]
		}
	}
	return pos + 1, k
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

// Shallow clone.
func Clone[S ~[]E, E any](s S) S {
	return append(s[:0:0], s...)
}

// Insert inserts the values v... into s at index i,
// !returning the modified slice.
// The elements at s[i:] are shifted up to make room.
// In the returned slice r, r[i] == v[0],
// and r[i+len(v)] == value originally at r[i].
// This function is O(len(s) + len(v)).
func Insert[S ~[]E, E any](s S, i int, v ...E) S {
	if i < 0 {
		i = 0
	}
	if i > len(s) {
		i = len(s)
	}

	m := len(v)
	if m == 0 {
		return s
	}
	n := len(s)
	if i == n {
		return append(s, v...)
	}
	if n+m > cap(s) {
		s2 := append(s[:i], make(S, n+m-i)...)
		copy(s2[i:], v)
		copy(s2[i+m:], s[i:])
		return s2
	}
	s = s[:n+m]
	if !overlaps(v, s[i+m:]) {
		copy(s[i+m:], s[i:])
		copy(s[i:], v)
		return s
	}
	copy(s[n:], v)
	rotateRight(s[i:], m)
	return s
}

func overlaps[E any](a, b []E) bool {
	if len(a) == 0 || len(b) == 0 {
		return false
	}
	elemSize := unsafe.Sizeof(a[0])
	if elemSize == 0 {
		return false
	}
	return uintptr(unsafe.Pointer(&a[0])) <= uintptr(unsafe.Pointer(&b[len(b)-1]))+(elemSize-1) &&
		uintptr(unsafe.Pointer(&b[0])) <= uintptr(unsafe.Pointer(&a[len(a)-1]))+(elemSize-1)
}

func rotateLeft[E any](s []E, r int) {
	for r != 0 && r != len(s) {
		if r*2 <= len(s) {
			swap(s[:r], s[len(s)-r:])
			s = s[:len(s)-r]
		} else {
			swap(s[:len(s)-r], s[r:])
			s, r = s[len(s)-r:], r*2-len(s)
		}
	}
}

func rotateRight[E any](s []E, r int) {
	rotateLeft(s, len(s)-r)
}

func swap[E any](x, y []E) {
	for i := 0; i < len(x); i++ {
		x[i], y[i] = y[i], x[i]
	}
}
func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
	if i < 0 {
		i = 0
	}
	if j > len(s) {
		j = len(s)
	}
	if i == j {
		return Insert(s, i, v...)
	}
	if j == len(s) {
		return append(s[:i], v...)
	}
	tot := len(s[:i]) + len(v) + len(s[j:])
	if tot > cap(s) {
		s2 := append(s[:i], make(S, tot-i)...)
		copy(s2[i:], v)
		copy(s2[i+len(v):], s[j:])
		return s2
	}
	r := s[:tot]
	if i+len(v) <= j {
		copy(r[i:], v)
		copy(r[i+len(v):], s[j:])
		// clear(s[tot:])
		return r
	}
	if !overlaps(r[i+len(v):], v) {
		copy(r[i+len(v):], s[j:])
		copy(r[i:], v)
		return r
	}
	y := len(v) - (j - i)
	if !overlaps(r[i:j], v) {
		copy(r[i:j], v[y:])
		copy(r[len(s):], v[:y])
		rotateRight(r[i:], y)
		return r
	}
	if !overlaps(r[len(s):], v) {
		copy(r[len(s):], v[:y])
		copy(r[i:j], v[y:])
		rotateRight(r[i:], y)
		return r
	}
	k := startIdx(v, s[j:])
	copy(r[i:], v)
	copy(r[i+len(v):], r[i+k:])
	return r
}

func startIdx[E any](haystack, needle []E) int {
	p := &needle[0]
	for i := range haystack {
		if p == &haystack[i] {
			return i
		}
	}
	panic("needle not found")
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class MyScanner {
        static BufferedReader r;
        static StringTokenizer st;
        public MyScanner() {
            r = new BufferedReader(new InputStreamReader(System.in));
        }
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (Exception e) {
                return null;
            }
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    static class Fenwick {
        int n;
        long[] a;

        public Fenwick(int n) {
            this.n = n;
            a = new long[n + 1];
        }

        void add(int x, Long v) {
            if (x == 0) throw new Error("下标不能为0");
            for (; x <= n; x += x & (-x)) {
                a[x] += v;
            }
        }

        long sum(int x) {
            if (x > n) throw new Error("下标越界");
            long ans = 0L;
            for (; x != 0; x -= x & (-x)) {
                ans += a[x];
            }
            return ans;
        }

        long rangeSum(int l, int r) {
            return sum(r) - sum(l - 1);
        }

        int query(long s) {
            int pos = 0, i = (int) (Math.log(n) / Math.log(2)) + 1;
            for (; i >= 0; i--) {
                if (pos + (1 << i) <= n && a[pos + (1 << i)] < s) {
                    pos += (1 << i);
                    s -= a[pos];
                }
            }
            return pos;
        }
    }
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static MyScanner sc = new MyScanner();
    static int N;
    static final int MAXN = 500010;
    static int[] p = new int[MAXN], ans = new int[MAXN];
    public static void main(String[] args) throws IOException {
        N = sc.nextInt();
        Fenwick tr = new Fenwick(N);
        for (int i = 1; i <= N; i++) {
            p[i] = sc.nextInt();
            tr.add(i, 1L);
        }
        for (int i = N; i >= 1; i--) {
            int idx = tr.query(p[i]) + 1;
            ans[idx] = i;
            tr.add(idx, -1L);
        }
        for (int i = 1; i <= N; i++) {
            bw.write(ans[i] + " ");
        }
        bw.flush();
    }
}

JavaScript solution:
"use strict";var c=Object.create;var p=Object.defineProperty;var f=Object.getOwnPropertyDescriptor;var C=Object.getOwnPropertyNames;var x=Object.getPrototypeOf,w=Object.prototype.hasOwnProperty;var y=(r,t,i,e)=>{if(t&&typeof t=="object"||typeof t=="function")for(let s of C(t))!w.call(r,s)&&s!==i&&p(r,s,{get:()=>t[s],enumerable:!(e=f(t,s))||e.enumerable});return r};var g=(r,t,i)=>(i=r!=null?c(x(r)):{},y(t||!r||!r.__esModule?p(i,"default",{value:r,enumerable:!0}):i,r));var a=r=>{let t=1;for(;t<r;)t*=2;return t},o=class{n;size;d;constructor(t){if(typeof t=="number")this.n=t,this.size=a(t),this.d=Array(this.size*2).fill(this.e());else{this.n=t.length,this.size=a(t.length),this.d=Array(this.size*2).fill(this.e());for(let i=0;i<t.length;i++)this.d[this.size+i]=t[i];for(let i=this.size-1;i>0;i--)this.d[i]=this.op(this.d[i*2],this.d[i*2+1])}}set(t,i){let e=t+this.size;for(this.d[e]=i,e>>=1;e>0;e>>=1)this.d[e]=this.op(this.d[e*2],this.d[e*2+1])}add(t,i){let e=t+this.size;for(this.d[e]=this.op(this.d[e],i),e>>=1;e>0;e>>=1)this.d[e]=this.op(this.d[e*2],this.d[e*2+1])}get(t){return this.d[t+this.size]}prod(t,i){let e=this.e(),s=this.e(),n=t+this.size,u=i+this.size;for(;n<u;)n&1&&(e=this.op(e,this.d[n++])),u&1&&(s=this.op(this.d[--u],s)),n>>=1,u>>=1;return this.op(e,s)}allProd(){return this.d[1]}maxRight(t,i){if(t===this.n)return this.n;let e=t+this.size,s=this.e();do{for(;~e&1;)e>>=1;if(!i(this.op(s,this.d[e]))){for(;e<this.size;){e<<=1;let n=this.op(s,this.d[e]);i(n)&&(s=n,e++)}return e-this.size}s=this.op(s,this.d[e]),e++}while((e&-e)!==e);return this.n}minLeft(t,i){if(t===0)return 0;let e=t+this.size,s=this.e();do{for(e--;e>1&&e&1;)e>>=1;if(!i(this.op(this.d[e],s))){for(;e<this.size;){e=e<<1|1;let n=this.op(this.d[e],s);i(n)&&(s=n,e--)}return e+1-this.size}s=this.op(this.d[e],s)}while((e&-e)!==e);return 0}};var d=g(require("node:fs")),l=class{buf;constructor(t=process.stdin.fd){this.buf=d.readFileSync(t,"utf8").split(/\s+/).reverse()}get str(){return this.buf.pop()}strs(t){return Array(t).fill(null).map(()=>this.str)}get num(){return Number(this.buf.pop())}nums(t){return Array(t).fill(null).map(()=>this.num)}num2d(t,i){return Array(t).fill(null).map(()=>this.nums(i))}get int(){return this.num}ints=this.nums;int2d=this.num2d;get ind(){return this.num-1}inds(t){return Array(t).fill(null).map(()=>this.ind)}ind2d(t,i){return Array(t).fill(null).map(()=>this.inds(i))}get bint(){return BigInt(this.buf.pop())}bints(t){return Array(t).fill(null).map(()=>this.bint)}bint2d(t,i){return Array(t).fill(null).map(()=>this.bints(i))}};var b=class{buf="";write(t,i=" "){Array.isArray(t)?this.buf=this.buf.concat(t.join(i)):this.buf=this.buf.concat(t.toString())}writeln(t,i=" "){this.write(t,i),this.write(`
`)}yn(t){t?this.yes():this.no()}yes(){this.write(`Yes
`)}no(){this.write(`No
`)}flush(){this.buf.length!==0&&(console.log(this.buf.trimEnd()),this.buf="")}};var m=r=>{let t=new l,i=new b,e=r(t,i);typeof e=="boolean"?i.yn(e):e!==void 0&&i.write(e),i.flush()};var h=class extends o{op(t,i){return t+i}e(){return 0}};m(r=>{let t=r.int,i=r.ints(t),e=new h(Array(t).fill(1)),s=Array(t).fill(-1);for(let n=t-1;n>=0;n--){let u=e.maxRight(0,T=>T<i[n]);s[u]=n+1,e.set(u,0)}return s});

Python solution:
class BinaryIndexedTree():
    def __init__(self, n):
        self.size = n
        self.tree = [0]*n
    
    def sum(self, i):
        i, res = i + 1, 0
        while i > 0:
            res += self.tree[i - 1]
            i -= i & -i
        return res
        
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i - 1] += x
            i += i & -i

    def lower_bound(self, x):
        i, index = 1, 0
        while i*2 <= self.size:
            i *= 2
        while i > 0:
            if index + i - 1 < self.size and x > self.tree[index + i - 1]:
                x -= self.tree[index + i - 1]
                index += i
            i //= 2
        return index


n = int(input())
p = list(map(int, input().split()))
bit = BinaryIndexedTree(n)
for i in range(n):
    bit.add(i, 1)

ans = [0]*n
c = list(range(n))
for i in range(n):
    a = p[n - 1 - i]
    j = bit.lower_bound(a)
    ans[j] = n - i
    bit.add(j, -1)

print(*ans)

Ruby solution:
class BIT
  attr_accessor :data, :size, :n

  def initialize(arg)
    case arg
    when Array
      @n = arg.size
      @size = 1 << n.bit_length
      @data = [0].concat(arg) + [0] * (@size - n)

      1.upto(@size) do |i|
        up = i + (i & -i)
        next if up > @size
        @data[up] += @data[i]
      end
    when Integer
      @n = arg
      @size = 1 << n.bit_length
      @data = [0] * @size
    end
  end

  def add(pos, value)
    idx = pos + 1
    while idx <= size
      data[idx] += value
      idx += idx & -idx
    end
  end

  def sum(l, r = nil)
    r ? _sum(r) - _sum(l) : _sum(l)
  end

  def kth(k)
    w = size
    i = 0
    while w > 0
      if (k > data[i + w])
        i += w
        k -= data[i]
      end
      w >>= 1
    end
    i
  end

  private
  def _sum(r)
    idx = r
    res = 0
    while idx > 0
      res += data[idx]
      idx -= idx & -idx
    end
    res
  end
end


N = gets.to_i
P = gets.split.map(&:to_i)
ft = BIT.new([1] * N)

ans = []
(N - 1).downto(0) do |i|
  idx = ft.kth(P[i])
  ans[idx] = i + 1
  ft.add(idx, -1)
end

puts ans.join(" ")