#P18392. Couleur

Couleur

Couleur

DreamGrid 有一个包含 nn 个整数的数组。他可以执行以下操作:选择一个此前尚未选择的元素,将其标记为不可用。DreamGrid 将恰好执行 nn 次操作,直到所有元素都不可用。

定义一个子数组的代价为其中的逆序对数量。在每次操作执行之前,DreamGrid 想知道:不包含任何不可用元素的子数组中,最大的代价是多少?

数组 al,al+1,…,ara_l,a_{l+1},\ldots,a_r 是原数组的一段连续子数组,其中 1≤l≤r≤n1\le l\le r\le n。其中的一个逆序对是满足 l≤i<j≤rl\le i<j\le r 且 ai>aja_i>a_j 的下标对 (i,j)(i,j)。相等的元素不构成逆序对。

输入格式

第一行包含整数 TT,表示测试用例数量。

对于每个测试用例:

  • 第一行包含整数 nn(1≤n≤1051\le n\le10^5),表示数组长度。
  • 第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤n1\le a_i\le n)。
  • 第三行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,用于表示删除下标的顺序。

第三行经过了加密。设第 ii 次操作前所求的答案为 ziz_i,则该操作实际选择的下标为 pi⊕zip_i\oplus z_i,其中 ⊕\oplus 表示按位异或。解密后的 nn 个下标构成 1,2,…,n1,2,\ldots,n 的一个排列。

保证所有测试用例的 nn 之和不超过 10610^6。原题没有单独规定 TT 的上限;由每例 n≥1n\ge1 可知 T≤106T\le10^6。

输出格式

对于每个测试用例,输出一行 nn 个整数 z1,z2,…,znz_1,z_2,\ldots,z_n,相邻整数用一个空格分隔。ziz_i 表示第 ii 次操作之前的答案。

原题明确要求行尾不要输出多余空格。

样例

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

样例说明

三个测试用例解密后的实际操作下标顺序分别为:

  • {2,4,5,3,1}\{2,4,5,3,1\};
  • {1,3,8,7,9,2,4,5,10,6}\{1,3,8,7,9,2,4,5,10,6\};
  • {15,12,2,1,9,6,11,14,3,13,4,5,8,7,10}\{15,12,2,1,9,6,11,14,3,13,4,5,8,7,10\}。