Deducing Sortability
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2900
Tags: binary search, bitmasks, math

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:

1. Choose an index $$$p$$$ ($$$1 \leq p \leq N$$$).
2. Let $$$c$$$ be the number of operations that have been done on index $$$p$$$ before this operation.
3. Decrease the value of $$$A_p$$$ by $$$2^c$$$.
4. 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 format:
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 format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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]$$$.

Example input:
6 3
1
4
5

Example output:
17
1
3
4

Example input:
1 0

Example output:
1

Editorial:
Define an array as distinctable if and only if Pak Chanek can do zero or more operations to make the elements of the array different from each other. Finding a sortable array $$$A$$$ of size $$$N$$$ with the minimum possible sum of elements is the same as finding a distinctable array $$$A$$$ of size $$$N$$$ with the minimum possible sum and permuting its elements.
Define a value $$$k'$$$ as being reachable from a value $$$k$$$ if and only if we can do zero or more operations to the value $$$k$$$ to turn it into $$$k'$$$.
To construct a distinctable array of size $$$N$$$ with the minimum possible sum, we can do a greedy method. Initially, the array $$$A$$$ is empty. Then, do the following iteration multiple times sequentially for each value $$$k$$$ from $$$1$$$, $$$2$$$, $$$3$$$, and so on until $$$A$$$ has $$$N$$$ elements:
1. Consider each value $$$k'$$$ that is reachable from $$$k$$$.
2. Let's say there are $$$w$$$ values $$$k'$$$ that has not been used as the final value for each of the previous elements of $$$A$$$.
3. Append $$$w$$$ new elements with value $$$k$$$ to $$$A$$$ and assign the final value for each of the new elements with each of the usable values of $$$k'$$$.
4. In the case where appending $$$w$$$ new elements makes the size of $$$A$$$ exceed $$$N$$$, we choose only some of the usable values of $$$k'$$$ to make the size of $$$A$$$ exactly $$$N$$$.
Notice that while choosing the final values for each value $$$k$$$, there is only one way to do it for each iteration except the last iteration. For the last iteration, it can be obtained that in order to get the lexicographically minimum array, we choose the usable final values that are the largest ones.
It can be obtained that each value that is reachable from $$$k$$$ is in the form of $$$x \times 2^y$$$ for some positive integer $$$x$$$ and some non-negative integer $$$y$$$ satisfying $$$x+y=k$$$.
For a pair $$$(x, y)$$$, if we choose an even integer for $$$x$$$, we can always find another pair $$$(x_2, y_2)$$$ such that $$$x_2 \times 2^{y_2} = x \times 2^y$$$ and $$$x_2+y_2 \leq x+y$$$. From the logic of the greedy method, we can see that choosing an even integer for $$$x$$$ is always not optimal.
For two distinct pairs $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, if both $$$x_1$$$ and $$$x_2$$$ are odd, then $$$x_1 \times 2^{y_1} \neq x_2 \times 2^{y_2}$$$ always holds.
Using the knowledge above, we can see that during the greedy method, the usable final values for a value $$$k$$$ are all the ones with odd values of $$$x$$$, which there are $$$\lceil \frac{k}{2} \rceil$$$ of them. From this, we can see that in our greedy method, we only do $$$O(\sqrt N)$$$ iterations. So, we can get the sum of elements in our constructed array $$$A$$$ in $$$O(\sqrt N)$$$.
To answer each query, we need to find the $$$P_i$$$-th smallest final value in the array and find which value produces it.
We can construct an array $$$F_0, F_1, F_2, \ldots$$$ of size $$$O(\sqrt N)$$$. This means for each $$$i$$$, there are $$$F_i$$$ values $$$x \times 2^y$$$ with $$$y=i$$$, namely the ones with the values of $$$x$$$ being the $$$F_i$$$ smallest positive odd integers.
We can convert each value $$$x \times 2^y$$$ into $$$x' \times 2^{y'}$$$ such that all values of $$$x'$$$ have the same MSB (Most Significant Bit). After converting, sorting the values $$$x' \times 2^{y'}$$$ is the same as sorting the pairs $$$(y', x')$$$.
We can construct a two-dimensional array $$$G$$$ of size $$$O(\sqrt N) \times O(\log N)$$$ with $$$G_{i,j}$$$ representing the number of final values with $$$y' = i$$$ and $$$y = i-j$$$.
To find the $$$P_i$$$-th smallest final value, firstly we find its value of $$$y'$$$ with binary search using array $$$G$$$.
Now, for some integer $$$d$$$, we need to find the $$$d$$$-th smallest value of $$$x'$$$ for all final values with a certain value of $$$y'$$$. To find it, we do a binary search on a value $$$m$$$ with each iteration checking whether there are at least $$$d$$$ values of $$$x'$$$ that are less than or equal to $$$m$$$. Each iteration of the binary search can be computed by iterating $$$O(\log N)$$$ values in $$$G$$$ and using simple math.
To find which value produces a certain final value, we just convert it back into $$$x \times 2^y$$$ and find the value of $$$x+y$$$.
Time complexity: $$$O(\sqrt N \log N + Q \log^2N)$$$
Challenge: find the solution for $$$N \leq 10^{18}$$$.