#P18022. Prefix MEX Equation
Prefix MEX Equation
Prefix MEX Equation
对于长度相同的两个数组 ,你可以执行任意次操作:选择一个下标 ,交换 和 。
一个整数集合的 MEX 是其中没有出现的最小非负整数。数组 的前缀 MEX 数组 定义为
如果存在一组上述交换操作,使得 和 的前缀 MEX 数组完全相同,则称 是一对好数组。也就是说,需要同一组交换使所有前缀同时满足要求。
给定两个长度为 的数组 ,求有多少对下标 满足 ,并且
$$(A_L,A_{L+1},\ldots,A_R),\quad(B_L,B_{L+1},\ldots,B_R)$$是一对好数组。
输入格式
第一行一个整数 。每组数据第一行一个整数 ,第二行 个整数 ,第三行 个整数 。
输出格式
每组数据输出一行一个整数,表示合法区间的数量。答案不取模。
数据范围
,,。所有测试用例的 之和不超过 。
样例 1
输入
3
4
0 2 1 0
0 1 0 2
3
1 2 1
2 1 1
4
0 0 3 1
2 0 1 1
输出
2
6
4