162 人解决，222 人已尝试。
175 份提交通过，共有 861 份提交。
3.5 EMB 奖励。
单点时限: 1.0 sec
内存限制: 256 MB
Given is a rooted tree with $n$ nodes. And for convenience，we set node $1$ as its root.
Moreover, the parent of the $i$-th node is $\lfloor \frac{i}{2} \rfloor $, where $2\le i\le n$.
Apparently, this is a binary tree, and for the $i$-th node, its left child is $2i$ and its right child is $2i+1$ (If it has the corresponding child).
Now, here come $m$ questions. The $i$-th question will ask you the rank of the $x_i$-th node in the preorder traversal of the tree.
As a promissing programmer, you’re not throwing away your shot. So you need to give the answer of every question.
Preorder Traversal：
Algorithm Preorder(tree)
Visit the root.
Traverse the left subtree, i.e., call Preorder(tree->left)
Traverse the right subtree, i.e., call Preorder(tree->right)
For example, when $n=10$, the preorder of the tree is ${1,2,4,8,9,5,10,3,6,7}$.
The first line contains $2$ integers $n,m\ (1\le n\le 10^{18},\ 1\le m\le 10^5)$, denoting the number of the nodes in this tree and the number of the questions, respectively.
Next $m$ lines, for $i$-th line, contains an integer $x_i\ (1\le x_i\le n)$ , denoting a question about the rank of node $x_i$ in the preorder of the tree.
For each question , output an integer, which represents your answer.
10 5 1 3 5 7 9
1 8 6 10 5
162 人解决，222 人已尝试。
175 份提交通过，共有 861 份提交。
3.5 EMB 奖励。
创建: 2 年前.
修改: 2 年前.
最后提交: 8 月前.
来源: N/A