标签：text Moscow 区间 leq minp Gorillas mex sim

D. Moscow Gorillas

In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $p$ of length $n$ to the zoo.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ occurs twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ is present in the array).

The gorillas had their own permutation $q$ of length $n$. They suggested that you count the number of pairs of integers $l, r$ ($1 \le l \le r \le n$) such that $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$.

The $\operatorname{MEX}$ of the sequence is the minimum integer positive number missing from this sequence. For example, $\operatorname{MEX}([1, 3]) = 2$, $\operatorname{MEX}([5]) = 1$, $\operatorname{MEX}([3, 1, 2, 6]) = 4$.

You do not want to risk your health, so you will not dare to refuse the gorillas.

Input

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the permutations length.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the elements of the permutation $p$.

The third line contains $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le n$) — the elements of the permutation $q$.

Output

Print a single integer — the number of suitable pairs $l$ and $r$.

Examples
input

3
1 3 2
2 1 3

output

2

input

7
7 3 6 2 1 5 4
6 7 2 5 3 1 4

output

16

input

6
1 2 3 4 5 6
6 5 4 3 2 1

output

11

Note

In the first example, two segments are correct – $[1, 3]$ with $\operatorname{MEX}$ equal to $4$ in both arrays and $[3, 3]$ with $\operatorname{MEX}$ equal to $1$ in both of arrays.

In the second example, for example, the segment $[1, 4]$ is correct, and the segment $[6, 7]$ isn't correct, because $\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$.

 

解题思路

　　比赛的时候想到了通过枚举$\text{mex}$来计算每个$\text{mex}$对答案的贡献是多少，但没写出来。

　　先考虑$\text{mex} = 1$的情况，首先选取的区间不能包含元素$1$，那么$p$和$q$中能够选取的区间就被分成了$3$个部分，长度分别为$s_1,s_2,s_3$：

　　那么很明显共有$\dfrac{s_1(s_1 + 1)}{2} + \dfrac{s_2(s_2 + 1)}{2} + \dfrac{s_3(s_3 + 1)}{2}$个区间使得$\text{mex}(p[l \sim r]) = \text{mex}(q[l \sim r]) = 1$。

　　下面考虑$\text{mex} > 1$的情况。

　　如果一个排列的区间满足$\text{mex}(p[l \sim r]) = i$，那么区间$[l, r]$一定包含元素$1 \sim i-1$且一定不包含元素$i$。定义$p_x$表示元素$x$在排列中的位置，$\text{minp}[i]$表示前$i$个元素中最小的下标位置，即$\text{minp}[i] = \min\limits_{1 \leq j \leq i} \{ p[j] \}$，同理$\text{maxp}[i] = \max\limits_{1 \leq j \leq i} \{ p[j] \}$。因此如果某个区间的$\text{mex} = i$，那么就要满足$p[i] < \text{minp}[i-1]$或者$p[i] > \text{maxp}[i-1]$，即$p[i]$不能在$\left[ \text{minp}[i-1], \text{maxp}[i-1] \right]$的范围内。

1. 如果$p_{i} < \text{minp}[i-1]$，那么满足$\text{mex}(p[l \sim r]) = i$的$l$和$r$要满足$p_i < l \leq \text{minp}[i-1]$，$\text{maxp}[i-1] \leq r \leq n$。
2. 如果$p_{i} > \text{maxp}[i-1]$，那么那么满足$\text{mex}(p[l \sim r]) = i$的$l$和$r$要满足$1 \leq l \leq \text{minp}[i-1]$，$\text{maxp}[i-1] \leq r < p[i]$。
3. 否则就是$\text{minp}[i-1] \leq p_{i} \leq \text{maxp}[i-1]$，此时没有区间满足$\text{mex}(p[l \sim r]) = i$。

　　现在是有两个排列$p$和$q$，那么对于同时满足$\text{mex}(p[l \sim r]) = i$和$\text{mex}(q[l \sim r]) = i$的区间可以对各自的$l$和$r$分别通过区间求交的方式得到：

　　在排列$p$中，$l_p$的取值范围是$[3,5]$（红色部分），$r_p$的取值范围是$[9,13]$（绿色部分）。在$q$中，$l_q$的取值范围是$[1,4]$（蓝色部分），$r_q$的取值范围是$[7,11]$（橙色部分）。

　　因此能够使得两个排列同时满足$\text{mex}(p[l \sim r]) = i$和$\text{mex}(q[l \sim r]) = i$的$l$要满足$l_p \cap l_q = [3,4]$，$r_p \cap r_q = [9,11]$（记得选取的区间一定使得两个排列都包含元素$1 \sim i-1$），那么满足的区间个数就是$| l_p \cap l_q | \times | r_p \cap r_q | = 2 \times 3 = 6$，即分别是区间$[3, 9]$、$[3,10]$、$[3, 11]$、$[4,9]$、$[4,10]$、$[4,11]$。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int p[N], q[N];
 9 int minp[N], maxp[N], minq[N], maxq[N];
10 
11 LL get(int a, int b, int c, int d) {    // 区间[a,b]和[c,d]求交集
12     return max(0, min(b, d) - max(a, c) + 1);
13 }
14 
15 LL cal(LL x) {  // 计算1+2+...+x
16     return x * (x + 1) >> 1;
17 }
18 
19 int main() {
20     int n;
21     scanf("%d", &n);
22     for (int i = 1; i <= n; i++) {
23         int x;
24         scanf("%d", &x);
25         p[x] = i;
26     }
27     for (int i = 1; i <= n; i++) {
28         int x;
29         scanf("%d", &x);
30         q[x] = i;
31     }
32     minp[1] = maxp[1] = p[1];
33     minq[1] = maxq[1] = q[1];
34     for (int i = 2; i <= n; i++) {
35         minp[i] = min(minp[i - 1], p[i]);
36         maxp[i] = max(maxp[i - 1], p[i]);
37         minq[i] = min(minq[i - 1], q[i]);
38         maxq[i] = max(maxq[i - 1], q[i]);
39     }
40     LL ret = 1; // 当两个排列都选区间[1,n]那么就有mex=n+1，这里的1就是指这个情况
41     for (int i = 2; i <= n; i++) {  // 考虑mex=2~n的情况
42         if (p[i] >= minp[i - 1] && p[i] <= maxp[i - 1] || q[i] >= minq[i - 1] && q[i] <= maxq[i - 1]) continue; // 某个排列无法取得mex=i的区间
43         int lp, rp, lq, rq;
44         if (p[i] > maxp[i - 1]) lp = 1, rp = p[i] - 1;  // p[i]在区间右边
45         else lp = p[i] + 1, rp = n; // p[i]在区间左边
46         if (q[i] > maxq[i - 1]) lq = 1, rq = q[i] - 1;  // q[i]在区间右边
47         else lq = q[i] + 1, rq = n; //q[i]在区间左边
48         ret += get(lp, minp[i - 1], lq, minq[i - 1]) * get(maxp[i - 1], rp, maxq[i - 1], rq);   // 区间求交，然后乘法原理计算答案
49     }
50     // 最后考虑mex=1的3个区间
51     ret += cal(get(1, p[1] - 1, 1, q[1] - 1)) + cal(max(0, abs(p[1] - q[1]) - 1)) + cal(get(p[1] + 1, n, q[1] + 1, n));
52     printf("%lld", ret);
53     
54     return 0;
55 }

 

参考资料

　　Codeforces Round #852 Editorial：https://codeforces.com/blog/entry/112723

　　Codeforces Round #852(Div. 2) D(枚举+分类讨论)：https://zhuanlan.zhihu.com/p/605710274

标签：text,Moscow,区间,leq,minp,Gorillas,mex,sim
From： https://www.cnblogs.com/onlyblues/p/17117210.html