#SYUCT13E. 镜面异或序列
镜面异或序列
题目描述
给定一个长度为 的非负整数序列
定义序列 的逆序对数量为
$$\operatorname{inv}(a) =\left|\left\{(i,j)\mid 1\le i<j\le n,\ a_i>a_j\right\}\right|.$$现在需要进行 次操作,所有操作均会永久生效。
共有两种操作:
-
1 x:对所有 ,同时执行其中 表示按位异或;
-
$$(a_1,a_2,\ldots,a_n) \longleftarrow (a_n,a_{n-1},\ldots,a_1).$$2:将整个序列翻转,即
对于每次操作,输出操作完成后当前序列的逆序对数量 。
输入格式
第一行输入一个整数 (),表示序列长度。
第二行输入 个整数 (),表示初始序列。
第三行输入一个整数 (),表示操作次数。
接下来 行,每行描述一次操作,为以下两种形式之一:
1 x();2。
输出格式
输出 行。第 行输出一个整数,表示第 次操作完成后当前序列的逆序对数量。
样例
4
2 0 3 2
3
1 1
2
1 2
2
3
2