#P18392. Couleur
Couleur
Couleur
DreamGrid 有一个包含 个整数的数组。他可以执行以下操作:选择一个此前尚未选择的元素,将其标记为不可用。DreamGrid 将恰好执行 次操作,直到所有元素都不可用。
定义一个子数组的代价为其中的逆序对数量。在每次操作执行之前,DreamGrid 想知道:不包含任何不可用元素的子数组中,最大的代价是多少?
数组 是原数组的一段连续子数组,其中 。其中的一个逆序对是满足 且 的下标对 。相等的元素不构成逆序对。
输入格式
第一行包含整数 ,表示测试用例数量。
对于每个测试用例:
- 第一行包含整数 (),表示数组长度。
- 第二行包含 个整数 ()。
- 第三行包含 个整数 ,用于表示删除下标的顺序。
第三行经过了加密。设第 次操作前所求的答案为 ,则该操作实际选择的下标为 ,其中 表示按位异或。解密后的 个下标构成 的一个排列。
保证所有测试用例的 之和不超过 。原题没有单独规定 的上限;由每例 可知 。
输出格式
对于每个测试用例,输出一行 个整数 ,相邻整数用一个空格分隔。 表示第 次操作之前的答案。
原题明确要求行尾不要输出多余空格。
样例
3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10
7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0
样例说明
三个测试用例解密后的实际操作下标顺序分别为:
- ;
- ;
- 。