← 返回题目列表

Codeforces · 414/C

C. Mashmokh 和反向操作

中文机器翻译题面 查看原题

Mashmokh 的老板 Bimokh 不喜欢 Mashmokh。于是他解雇了他。 Mashmokh 决定去读大学并参加 ACM,而不是找一份新工作。他想成为巴莫克团队的一员。为了加入,他被分配了一些编程任务并需要一周的时间来解决这些任务。 Mashmokh 并不是一位经验丰富的程序员。事实上他根本不是一个程序员。所以他没能解决这些问题。这就是为什么他要求你帮助他完成这些任务。其中一项任务如下。

你有一个长度为 2n 的数组 a 和 m 个查询。第 i 个查询由整数 qi 描述。为了执行第 i 个查询,您必须:

- 将数组分成 2n - qi 部分,其中每个部分是由 2qi 数字组成的子数组;第 j 个子数组 (1 ≤ j ≤ 2n - qi) 应包含元素a[(j - 1)·2qi + 1], a[(j - 1)·2qi + 2], ..., a[(j - 1)·2qi + 2qi];
- 反转每个子数组;
- 以相同的顺序将它们连接成一个数组(该数组成为新数组 a);
- 输出新a中的反转次数。

给定初始数组 a 和所有查询。回答所有问题。请注意,某些查询的更改将被保存以供进一步查询。

输入

输入的第一行包含一个整数 n (0 ≤ n ≤ 20)。

输入的第二行包含 2n 个空格分隔的整数 a[1], a[2], ..., a[2n] (1 ≤ a[i] ≤ 109),即初始数组。

输入的第三行包含一个整数 m (1 ≤ m ≤ 106)。

输入的第四行包含 m 个空格分隔的整数 q1, q2, ..., qm (0 ≤ qi ≤ n),查询。

注意:由于输入和输出的大小可能非常大,因此请勿在您的语言中使用慢速输出技术。例如,不要在 C++ 中使用输入和输出流(cin、cout)。

输出

输出 m 行。在第 i 行中打印第 i 个查询的答案(反转次数)。

示例

输入 #1

2
2 1 4 3
4
1 2 0 2

输出 #1

0
6
6
0

输入 #2

1
1 2
3
0 1 1

输出 #2

0
1
0

注意

如果我们反转数组 x[1], x[2], ..., x[n],它将变成新数组 y[1], y[2], ..., y[n],其中对于每个 i,y[i] = x[n - i + 1]。

数组 x[1]、x[2]、...、x[n] 的反转次数是满足以下条件的索引 i、j 对的数量:i < j 且 x[i] > x[j]。