#SYUCT13E. 镜面异或序列

镜面异或序列

题目描述

给定一个长度为 nn 的非负整数序列

a=(a1,a2,…,an).a=(a_1,a_2,\ldots,a_n).

定义序列 aa 的逆序对数量为

$$\operatorname{inv}(a) =\left|\left\{(i,j)\mid 1\le i<j\le n,\ a_i>a_j\right\}\right|.$$

现在需要进行 mm 次操作,所有操作均会永久生效。

共有两种操作:

  1. 1 x:对所有 1≤i≤n1\le i\le n,同时执行

    ai←ai⊕x,a_i\leftarrow a_i\oplus x,

    其中 ⊕\oplus 表示按位异或;

  2. 2:将整个序列翻转,即

    $$(a_1,a_2,\ldots,a_n) \longleftarrow (a_n,a_{n-1},\ldots,a_1).$$

对于每次操作,输出操作完成后当前序列的逆序对数量 inv⁡(a)\operatorname{inv}(a)。

输入格式

第一行输入一个整数 nn(1≤n≤2×1051\le n\le 2\times 10^5),表示序列长度。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<2200\le a_i<2^{20}),表示初始序列。

第三行输入一个整数 mm(1≤m≤2×1051\le m\le 2\times 10^5),表示操作次数。

接下来 mm 行,每行描述一次操作,为以下两种形式之一:

  • 1 x(0≤x<2200\le x<2^{20});
  • 2。

输出格式

输出 mm 行。第 ii 行输出一个整数,表示第 ii 次操作完成后当前序列的逆序对数量。

样例

4
2 0 3 2
3
1 1
2
1 2
2
3
2

下载正式赛最终版 PDF 题面