题目描述

难度分:$1800$

输入$n(1 \leq n \leq 2 \times 10^5)$和两个$1$~$n$的排列$p$和$q$。

定义$mex(a)$为不在$a$中的最小正整数。注意是正整数。定义$A[i..j]$表示$A$中下标从$i$到$j$的子数组。

输出有多少个下标对$(i,j)$，满足$i \leq j$且$mex(p[i..j])=mex(q[i..j])$。

输入样例$1$

3
1 3 2
2 1 3

输出样例$1$

2

输入样例$2$

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

输出样例$2$

16

输入样例$3$

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

输出样例$3$

11

算法

数学+双指针

依次考虑如下情况的贡献：

• 不含$1$的子数组对有多少个？
• 含$1$不含$2$的子数组对有多少个？
• 含$1,2$不含$3$的子数组对有多少个？

……

• 含$1,2,…,n-1$不含$n$的子数组对有多少个？
• 包含所有数的子数组对，这个很容易，就是整个数组，答案是$1$个。

设维护包含$p$中$1,2,…,v-1$的最小子数组的左端点$l_1$和右端点 $r_1$。维护包含$q$中$1,2,…,v-1$的最小子数组的左端点$l_2$和右端点$r_2$。

设$pos_1[v]$为$v$在$p$中的下标，$pos_2[v]$为$v$在$q$中的下标。（下标从$0$开始）对于不含$v$的方案数：

1. 设$l=-1$，如果$pos_1[v] \lt l_1$，那么$l=pos_1[v]$，如果$pos_2[v] \lt l_2$，那么$l$和$pos_2[v]$取$max$。

2. 设$r=n$，如果$pos_1[v] \gt r_1$，那么$r=pos_1[v]$，如果$pos_2[v] \gt r_2$，那么$r$和$pos_2[v]$取$min$。

子数组的左端点可以从$l+1$到$min(l_1,l_2)$，有$max(min(l_1, l_2)-l, 0)$个。

子数组的右端点可以从$max(r_1,r_2)$到$r-1$，有$max(r-max(r_1, r_2), 0)$个。方案数为$max(min(l_1, l_2)-l, 0) \times max(r-max(r_1, r_2), 0)$，把所有$v$的贡献都累加起来就是答案。

复杂度分析

时间复杂度

从$v=2$开始遍历到$n$，每次计算包含$[1,v-1]$不包含$v$的贡献时间复杂度为$O(1)$。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

在整个过程中开辟了$pos_1$数组和$pos_2$数组分别用于存$p$、$q$两个排列中各个元素的位置，它们的空间都是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, pos1[N], pos2[N];

int main() {
    scanf("%d", &n);
    for(int i = 0, v; i < n; i++) {
        scanf("%d", &v);
        pos1[v] = i;
    }
    for(int i = 0, v; i < n; i++) {
        scanf("%d", &v);
        pos2[v] = i;
    }
    LL i = pos1[1], j = pos2[1];
    LL l1 = i, r1 = i, l2 = j, r2 = j;
    if(i > j) swap(i, j);
    LL ans = i * (i + 1) / 2 + (j - i - 1) * (j - i) / 2 + (n - j - 1) * (n - j) / 2 + 1;
    for(int v = 2; v <= n; v++) {
        i = pos1[v], j = pos2[v];
        if(!(l1 < i && i < r1 || l2 < j && j < r2)) {
            LL l = -1;
            if(i < l1) {
                l = i;
            }
            if(j < l2) {
                l = max(l, j);
            }
            LL r = n;
            if(i > r1) {
                r = i;
            }
            if(j > r2) {
                r = min(r, j);
            }
            ans += max(min(l1, l2) - l, 0LL) * max(r - max(r1, r2), 0LL);
        }
        l1 = min(l1, i);
        r1 = max(r1, i);
        l2 = min(l2, j);
        r2 = max(r2, j);
    }
    printf("%lld\n", ans);
    return 0;
}