P16333 [DSDOI Round 1] 邓少分小组

邓少是一个学校的老师，他需要给学生分组。

具体地，邓少有 $n$ 个学生，编号为 $1,2,3,\dots,n$。邓少需要选出其中连续的一部分人分组成一个小组，具体地，他需要选出一个区间 $[L,R]$，让编号在 $L$ 到 $R$ 之间的人组成一个小组。 邓少让每个人选出一个喜欢的人，记 $A_i$ 表示编号为 $i$ 的人喜欢的人，邓少要求 $A$ 是一个**排列**。 同时，邓少给每个人选择了一个伙伴，记 $B_i$ 表示编号为 $i$ 的人的伙伴，邓少保证了 $B$ 是一个**排列**。 邓少希望能让同学和自己喜欢的人在一组，于是他希望：如果他选择的人的编号区间是 $[L,R]$，那么有 $\forall i\in[L,R],A_i\in[L,R]$。 同学们希望自己喜欢的人与自己喜欢的人的伙伴在一组，他们希望：如果邓少选择的人的编号区间是 $[L,R]$，那么有 $\forall i\in[L,R],B_{A_i}\in[L,R]$。 邓少当然知道同学们的心思，他想知道，有多少种选出**一个**小组的方式，使得选出的这个小组满足邓少和同学们的要求。 ### 形式化题意 给定一个正整数 $n$ 和两个排列 $A,B$ ，求有多少个区间 $[L,R]$ 满足： - $\forall i\in[L,R],A_i \in [L,R]$。 - $\forall i\in[L,R],B_{A_i} \in [L,R]$。

**本题有多组测试数据。** 第一行包含一个正整数 $t$，表示测试数据组数。 接下来包含 $t$ 组数据，每组数据的格式如下： 第一行包含一个正整数 $n$，表示学生数量。 第二行包含 $n$ 个正整数，表示排列 $A$。 第三行包含 $n$ 个正整数，表示排列 $B$。

对于每组测试数据，输出一行，包含一个正整数，表示方案数。

### 【样例解释】 对于样例一的三组测试数据，符合条件的选取方法分别是： - $[1,3],[4,5],[1,5]$。 - $[2,2],[1,3]$。 - $[3,3],[4,5],[3,5],[1,7]$。 容易发现没有其他区间满足要求。 ### 【数据范围】 对于所有测试数据，保证： - $1 \le T \le 5$； - $1 \le n \le 5 \times 10^5$； - 给出的 $A$ 和 $B$ 分别为长度为 $n$ 的全排列。 | 测试点编号 | $n \le$ | 特殊性质 | | :-: | :-: | :-: | | $1 \sim 3$ | $500$ | $-$ | | $4 \sim 6$ | $10^5$ | $A$ | | $7 \sim 20$ | $5 \times 10^5$ | $-$ | - 特殊性质 $A$：保证 $A_i=i$。