CF414C Mashmokh and Reverse Operation

Mashmokh 的老板 Bimokh 不喜欢 Mashmokh，于是解雇了他。Mashmokh 决定去上大学，并参加 ACM，而不是再找一份新工作。他想成为 Bamokh 团队的一员。为了加入团队，他被布置了一些编程任务，并且有一周的时间完成。Mashmokh 不是一个很有经验的程序员，事实上他根本就不会编程。因此，他没能解决这些题目，所以他请你帮他完成这些任务。其中有一道题的描述如下。 你有一个长度为 $2^n$ 的数组 $a$，以及 $m$ 个关于该数组的查询。第 $i$ 个查询由一个整数 $q_i$ 描述。每当你执行第 $i$ 个查询时，需要如下操作： - 将数组分成 $2^{n-q_i}$ 部分，每一部分是 $2^{q_i}$ 个数的连续子数组。对于第 $j$ 个子数组（$1 \leq j \leq 2^{n-q_i}$），它包含了 $a[(j-1)·2^{q_{i}}+1], a[(j-1)·2^{q_{i}}+2], \dots, a[(j-1)·2^{q_{i}}+2^{q_{i}}]$ 这些元素； - 反转每一个子数组； - 按照原顺序把所有子数组连接成一个新数组（该数组成为新的 $a$）； - 输出新数组 $a$ 中的逆序对个数。 给定初始数组 $a$ 和所有查询，请你回答所有查询。请注意，每次查询的更改会影响后续查询。

输入的第一行为一个整数 $n$，满足 $0 \leq n \leq 20$。 第二行为 $2^n$ 个用空格分隔的整数 $a[1],a[2],...,a[2^{n}]$，其中 $1 \leq a[i] \leq 10^9$，这是初始数组。 第三行为一个整数 $m$，满足 $1 \leq m \leq 10^6$。 第四行为 $m$ 个用空格分隔的整数 $q_1,q_2,\dots,q_m$，其中 $0 \leq q_i \leq n$，表示每次查询。 注意：由于输入输出的规模可能非常大，请不要在程序中使用低效的输入输出方式。例如，在 C++ 中不要使用输入输出流（cin, cout）。

输出 $m$ 行，第 $i$ 行输出第 $i$ 次查询后数组的逆序对数量。

如果我们反转一个数组 $x[1],x[2],...,x[n]$，则它变为数组 $y[1],y[2],...,y[n]$，其中 $y[i]=x[n-i+1]$。 对于数组 $x[1],x[2],...,x[n]$，逆序对的数量定义为满足 $ix[j]$ 的索引对 $(i,j)$ 的数量。 由 ChatGPT 5 翻译