https://codeforces.com/contest/1793/problem/D
对于给定的两个长度为 \(n\) 的排列 \(a_i, b_i\)，定义 \(MEX(S)\) 为集合 \(S\) 中没有出现的最小的正整数，找出所有满足 \(MEX(a_l, a_{l + 1}, \cdots, a_r) = MEX(b_l, b_{l + 1}, \cdots, b_r)\) 的区间 \([l, r]\) 的数量
记 \(MEX(a_l, a_{l + 1}, \cdots, a_r) = MEX(b_l, b_{l + 1}, \cdots, b_r) = M\)，考虑枚举 \(M\)，计算符合条件的 \([l, r]\) 的数量，那么我们就必须使得两个排列都包含 \([1, M - 1]\) 的所有数，且不能包含 \(M\)，我们可以找到这样一个极小的区间满足上述条件，若 \(M\) 在这个区间的外面，那么我们可以直接得出这个区间可以扩展到多大，这样 \(l\) 和 \(r\) 都可以在一个区间内任意取值，并使得两个区间均不包含 \(M\)，由于包含 \([1, M - 1]\) 的极小区间满足线性关系，于是这个过程可以用线性的复杂度处理
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
const int mod = 998244353, inf = 0x3f3f3f3f;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(), a[n + 1], b[n + 1];
for (int i = 1; i <= n; i++) a[read()] = i;
for (int i = 1; i <= n; i++) b[read()] = i;
int t1 = std::min(a[1], b[1]), t2 = std::max(a[1], b[1]);
i64 ans = 1ll;
ans += 1ll * t1 * (t1 - 1) / 2ll;
ans += 1ll * (t2 - t1) * (t2 - t1 - 1) / 2ll;
ans += 1ll * (n - t2 + 1) * (n - t2) / 2ll;
int la = a[1], ra = a[1], lb = b[1], rb = b[1];
for (int i = 2; i <= n; i++) {
int lmin = std::min(la, lb), rmax = std::max(ra, rb);
la = std::min(la, a[i]); ra = std::max(ra, a[i]);
lb = std::min(lb, b[i]); rb = std::max(rb, b[i]);
if (lmin <= a[i] && a[i] <= rmax || lmin <= b[i] && b[i] <= rmax) continue;
if (std::max(a[i], b[i]) < lmin) ans += 1ll * (lmin - std::max(a[i], b[i])) * (n - rmax + 1);
if (std::min(a[i], b[i]) > rmax) ans += 1ll * (std::min(a[i], b[i]) - rmax) * lmin;
if (a[i] < lmin && b[i] > rmax) ans += 1ll * (lmin - a[i]) * (b[i] - rmax);
if (b[i] < lmin && a[i] > rmax) ans += 1ll * (lmin - b[i]) * (a[i] - rmax);
}
printf("%lld", ans);
return 0;
}