Deducing Sortability (Codeforces 1725D)
Tags: Math, bitmasks

Let's say Pak Chanek has an array $$$A$$$ consisting of $$$N$$$ positive integers. Pak Chanek will do a number of operations. In each operation, Pak Chanek will do the following:   Choose an index $$$p$$$ ($$$1 \leq p \leq N$$$).  Let $$$c$$$ be the number of operations that have been done on index $$$p$$$ before this operation.  Decrease the value of $$$A_p$$$ by $$$2^c$$$.  Multiply the value of $$$A_p$$$ by $$$2$$$. After each operation, all elements of $$$A$$$ must be positive integers.An array $$$A$$$ is said to be sortable if and only if Pak Chanek can do zero or more operations so that $$$A_1 < A_2 < A_3 < A_4 < \ldots < A_N$$$.Pak Chanek must find an array $$$A$$$ that is sortable with length $$$N$$$ such that $$$A_1 + A_2 + A_3 + A_4 + \ldots + A_N$$$ is the minimum possible. If there are more than one possibilities, Pak Chanek must choose the array that is lexicographically minimum among them.Pak Chanek must solve the following things:   Pak Chanek must print the value of $$$A_1 + A_2 + A_3 + A_4 + \ldots + A_N$$$ for that array.  $$$Q$$$ questions will be given. For the $$$i$$$-th question, an integer $$$P_i$$$ is given. Pak Chanek must print the value of $$$A_{P_i}$$$. Help Pak Chanek solve the problem.Note: an array $$$B$$$ of size $$$N$$$ is said to be lexicographically smaller than an array $$$C$$$ that is also of size $$$N$$$ if and only if there exists an index $$$i$$$ such that $$$B_i < C_i$$$ and for each $$$j < i$$$, $$$B_j = C_j$$$.

Input: The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N \leq 10^9$$$, $$$0 \leq Q \leq \min(N, 10^5)$$$) — the required length of array $$$A$$$ and the number of questions.The $$$i$$$-th of the next $$$Q$$$ lines contains a single integer $$$P_i$$$ ($$$1 \leq P_1 < P_2 < \ldots < P_Q \leq N$$$) — the index asked in the $$$i$$$-th question.

Output: Print $$$Q+1$$$ lines. The $$$1$$$-st line contains an integer representing $$$A_1 + A_2 + A_3 + A_4 + \ldots + A_N$$$. For each $$$1 \leq i \leq Q$$$, the $$$(i+1)$$$-th line contains an integer representing $$$A_{P_i}$$$.

Note: In the first example, the array $$$A$$$ obtained is $$$[1, 2, 3, 3, 4, 4]$$$. We can see that the array is sortable by doing the following operations:   Choose index $$$5$$$, then $$$A = [1, 2, 3, 3, 6, 4]$$$.  Choose index $$$6$$$, then $$$A = [1, 2, 3, 3, 6, 6]$$$.  Choose index $$$4$$$, then $$$A = [1, 2, 3, 4, 6, 6]$$$.  Choose index $$$6$$$, then $$$A = [1, 2, 3, 4, 6, 8]$$$. 

Sample Inputs:
6 3
1
4
5

1 0

Sample Outputs:
17
1
3
4

1

Solution (Python):
def ev(x):
    k = 0
    while x % 2 == 0:
        x //= 2
        k += 1
    return x + k
(p, q) = [int(i) for i in input().split()]
(t, s, sum) = (1, 1, 0)
while True:
    ss = s + (t + 1) // 2
    if ss > p:
        m = p - s + 1
        sum += m * t
        break
    sum += t * ((t + 1) // 2)
    s = ss
    t += 1
mx = t - 2 * m + 1
print(sum)
(mul, ded, turn) = (0, 0, 0)
t -= 0 if mx == turn else 1
for i in range(q):
    x = int(input())
    if x == 1:
        print(1)
        continue
    while True:
        if x - ded <= t:
            print(ev(x - ded) + mul)
            break
        ded += (t + 1) // 2
        turn += 1
        mul += 1
        t -= 0 if mx == turn else 1

Solution (Python):
def ev(x):
    k = 0
    while x % 2 == 0:
        x //= 2
        k += 1
    return x + k
(p, q) = [int(i) for i in input().split()]
(t, s, sum) = (1, 1, 0)
while True:
    ss = s + (t + 1) // 2
    if ss > p:
        m = p - s + 1
        sum += m * t
        break
    sum += t * ((t + 1) // 2)
    s = ss
    t += 1
mx = t - 2 * m + 1
print(sum)
(mul, ded, turn) = (0, 0, 0)
t -= 0 if mx == turn else 1
for i in range(q):
    x = int(input())
    if x == 1:
        print(1)
        continue
    while True:
        if x - ded <= t:
            print(ev(x - ded) + mul)
            break
        ded += (t + 1) // 2
        turn += 1
        mul += 1
        t -= 0 if mx == turn else 1

Solution (Python):
def ev(x):
    k = 0
    while x % 2 == 0:
        x //= 2
        k += 1
    return x + k
(p, q) = [int(i) for i in input().split()]
(t, s, sum) = (1, 1, 0)
while True:
    ss = s + (t + 1) // 2
    if ss > p:
        m = p - s + 1
        sum += m * t
        break
    sum += t * ((t + 1) // 2)
    s = ss
    t += 1
mx = t - 2 * m + 1
print(sum)
(mul, ded, turn) = (0, 0, 0)
t -= 0 if mx == turn else 1
for i in range(q):
    x = int(input())
    if x == 1:
        print(1)
        continue
    while True:
        if x - ded <= t:
            print(ev(x - ded) + mul)
            break
        ded += (t + 1) // 2
        turn += 1
        mul += 1
        t -= 0 if mx == turn else 1