Restore Permutation (Codeforces 1208D)
Tags: Greedy, binary search

An array of integers $$$p_{1},p_{2}, \ldots,p_{n}$$$ is called a permutation if it contains each number from $$$1$$$ to $$$n$$$ exactly once. For example, the following arrays are permutations: $$$[3,1,2], [1], [1,2,3,4,5]$$$ and $$$[4,3,1,2]$$$. The following arrays are not permutations: $$$[2], [1,1], [2,3,4]$$$.There is a hidden permutation of length $$$n$$$.For each index $$$i$$$, you are given $$$s_{i}$$$, which equals to the sum of all $$$p_{j}$$$ such that $$$j < i$$$ and $$$p_{j} < p_{i}$$$. In other words, $$$s_i$$$ is the sum of elements before the $$$i$$$-th element that are smaller than the $$$i$$$-th element.Your task is to restore the permutation.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the size of the permutation.The second line contains $$$n$$$ integers $$$s_{1}, s_{2}, \ldots, s_{n}$$$ ($$$0 \le s_{i} \le \frac{n(n-1)}{2}$$$).It is guaranteed that the array $$$s$$$ corresponds to a valid permutation of length $$$n$$$.

Output: Print $$$n$$$ integers $$$p_{1}, p_{2}, \ldots, p_{n}$$$ — the elements of the restored permutation. We can show that the answer is always unique.

Note: In the first example for each $$$i$$$ there is no index $$$j$$$ satisfying both conditions, hence $$$s_i$$$ are always $$$0$$$.In the second example for $$$i = 2$$$ it happens that $$$j = 1$$$ satisfies the conditions, so $$$s_2 = p_1$$$.In the third example for $$$i = 2, 3, 4$$$ only $$$j = 1$$$ satisfies the conditions, so $$$s_2 = s_3 = s_4 = 1$$$. For $$$i = 5$$$ all $$$j = 1, 2, 3, 4$$$ are possible, so $$$s_5 = p_1 + p_2 + p_3 + p_4 = 10$$$.

Sample Inputs:
3
0 0 0

2
0 1

5
0 1 1 1 10

Sample Outputs:
3 2 1

1 2

1 4 3 2 5

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def update(i, v):
    while i <= z:
        tree[i] += v
        i += i & -i

def binary(num):
    f = 1
    l = z
    while f != l:
        mid = (f + l) // 2
        if tree[mid] < num:
            num -= tree[mid]
            f = mid + 1
        else:
            l = mid
    return f
n = int(input())
a = list(map(int, input().split()))
z = int(log2(n)) + 1
z = 1 << z
tree = [0] * (z + 1)
for i in range(1, n + 1):
    update(i, i)
ans = []
for i in reversed(a):
    x = binary(i + 1)
    ans.append(x)
    update(x, -x)
print(*ans[::-1])

Solution (Python):
n = int(input())
P = [int(i) for i in input().split()]
import math
import bisect
n_max = 2 * 10 ** 5
nn = int(math.log2(n_max)) + 1
BIT = [0] * (2 ** nn + 1)

def bitsum(BIT, i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s

def bitadd(BIT, i, x):
    if i <= 0:
        return True
    else:
        while i <= 2 ** nn:
            BIT[i] += x
            i += i & -i
        return BIT

def bitlowerbound(BIT, s):
    if s <= 0:
        return 0
    else:
        ret = 0
        k = 2 ** nn
        while k > 0:
            if k + ret <= 2 ** nn and BIT[k + ret] < s:
                s -= BIT[k + ret]
                ret += k
            k //= 2
        return ret + 1
for i in range(n_max):
    bitadd(BIT, i + 1, i + 1)
Ans = []
for i in reversed(range(n)):
    p = P[i]
    ans = bitlowerbound(BIT, p + 1)
    Ans.append(ans)
    bitadd(BIT, ans, -ans)
Ans = Ans[::-1]
print(*Ans)

Solution (Python):
from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(rd())
bit = [0] * 200005

def add(x, val):
    while x <= n:
        bit[x] += val
        x += x & -x

def query(x):
    num = 0
    for i in range(30, -1, -1):
        if num + (1 << i) <= n and bit[num + (1 << i)] <= x:
            x -= bit[num + (1 << i)]
            num += 1 << i
    return num + 1
for i in range(1, n + 1):
    add(i, i)
s = list(rrd())
ans = []
for i in range(len(s) - 1, -1, -1):
    q = query(s[i])
    ans.append(q)
    add(q, -q)
ans = ans[::-1]
print(*ans)