Min or Max 2
故事还在继续。现在小青鱼已经掌握了最小值和最大值的概念,想通过一些整数二元组练习自己的理解。
给定两个长度为 n 的序列 a1,a2,…,an 和 b1,b2,…,bn,它们分别都是 1,2,…,n 的排列。
初始有二元组 (x,y)=(a1,b1)。接着,按照 i=2,3,…,n 的顺序,对于每一个 i,必须恰好选择并执行下面两种操作中的一种:
- 将 x 更新为 min(x,ai),同时将 y 更新为 min(y,bi);
- 将 x 更新为 max(x,ai),同时将 y 更新为 max(y,bi)。
两坐标必须同时取最小值或同时取最大值;不能分别独立选择。
全部 n−1 次操作完成后,会得到一个最终二元组 (x,y)。请对每个 k=0,1,…,n−1,求满足 ∣x−y∣=k 的不同最终二元组的个数。不同操作序列得到相同二元组时只计一次。
输入格式
第一行包含整数 T,表示测试用例数,1≤T≤105。
对于每个测试用例:
- 第一行包含整数 n,2≤n≤5×105;
- 第二行包含 n 个整数 a1,…,an;
- 第三行包含 n 个整数 b1,…,bn。
a 和 b 分别是 1,2,…,n 的排列:所有元素均在 [1,n] 中,且每个序列内任意两个元素不同。
保证同一输入文件中所有测试用例的 n 之和不超过 5×105。
输出格式
对于每个测试用例输出一行 n 个整数,第 i 个整数表示 k=i−1 时的答案。
样例
输入:
4
2
1 2
2 1
5
2 4 1 5 3
2 4 1 5 3
5
1 2 3 4 5
5 4 3 2 1
8
5 8 3 4 2 7 1 6
4 6 3 8 5 1 2 7
输出:
2 0
5 0 0 0 0
2 2 2 2 0
5 5 2 2 1 0 0 0