单点时限: 2.0 sec
内存限制: 512 MB
This question is similar to Move The Numbers.
A permutation of size $2^n$ is an array of size $2^n$ such that each integer from $1$ to $2^n$ occurs exactly once in this array.
An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i>j$ and $a_i\leq a_j$. For example, a permutation $[4, 1, 3, 2]$ contains $4$ inversions: $(2, 1), (3, 1), (4, 1), (4, 3)$.
You are given a permutation $a$ of size $2^n$ and $m$ queries to it. Each query is represented by one number $t(0\leq t\leq n)$ denoting that you have to reverse the segment $[1,2^t],[2^t+1,2\times 2^t],[2\times 2^t+1,3\times 2^t],\cdots,[2^n-2^t+1,2^n]$ of the permutation.
For example, if $a = [1, 2, 3, 4, 5, 6, 7, 8]$ and a query $t=1$ is applied, then the resulting permutation is $[2, 1, 4, 3, 6, 5, 8, 7]$.
After each query you have to answer the number of inversions.
There are multiple test cases in this problem. $(T\leq 12)$
In each test case,The first line contains two integers $n$ and $m$.($2\leq n\leq 17, 3\leq m\leq 10000)$.
The second line contains $2^n$ integers $a_1,a_2,\cdots,a_{2^n}(1\leq a_i \leq 2^n)$ — the elements of the permutation. These integers are pairwise distinct.
The third line contains $m$ integers $t_1, t_2,\cdots,t_m (0\leq t_i\leq n)$.
For each testcase print $m$ lines denoting the answer.
2 3 4 3 2 1 1 1 0 2 3 1 4 2 3 0 1 2
4 6 6 2 4 2