https://codeforces.com/contest/1793/problem/D
不妨枚举 MEX(...) 的值 x。此时对于序列 [l, r]，需要满足：两个序列的 1 到 x - 1 都在这个区间内，并且 x 都不在这个区间内。
对于第一个条件，我们可以按照顺序处理两个序列的 1 到 x - 1 的最左边位置和最右边位置，显然可以在枚举的过程中 O(1) 处理。我们可以对 x = 1 的情况进行特殊处理，在此之后，这个区间就必须要包含至少一个值，假设此时左端点要落在 [1, L] 内，右端点要落在 [R, n] 内，那么 L <= R 成立。
接下来考虑第二个要求：不能包括两个位置。我们对其中一个位置 p 进行分析：
1) L <= p <= R，此时序列一定会包含 p，方案数为 0。
2) p < L，此时左端点不能到 p 的左边，那么需要将左端点更新为 [p + 1, L]。 p > R 同理。
最后只要将左右端点的区间长度相乘就是 MEX(...) 为 x 时的答案了。
转自 ：作者：tiger_2005 https://www.bilibili.com/read/cv21786337 出处：bilibili 侵删
int A[200010], B[200010], N;
int idxA[200010], idxB[200010];
long long cnt1 (int p) {
return 1ll * p * (p + 1) / 2;
}
int main(){
cin >> N;
readI(1, N, A);
readI(1, N, B);
long long ans = 1; // whole array
for (int i = 1; i <= N; i ++) {
idxA[A[i]] = i;
idxB[B[i]] = i;
}
int L = N, R = 1;
for (int i = 1; i <= N; i ++) {
int p = idxA[i], q = idxB[i];
if (p > q)
swap(p, q);
if (i == 1) {
if (p == q)
ans += cnt1(p - 1) + cnt1(N - p);
else
ans += cnt1(p - 1) + cnt1 (q - p - 1) + cnt1(N - q);
}
else {
L = min(L, idxA[i-1]);
R = max(R, idxA[i-1]);
L = min(L, idxB[i-1]);
R = max(R, idxB[i-1]);
// consider l in [1, L] ans r in [R, N]
// printf("- %d %d %d\n", i, L, R);
int lr = L, rl = R;
int ll = 1, rr = N;
if ((L <= p && p <= R) || (L <= q && q <= R))
continue;
if (p < L)
ll = max(ll, p + 1);
if (p > R)
rr = min(rr, p - 1);
if (q < L)
ll = max(ll, q + 1);
if (q > R)
rr = min(rr, q - 1);
ans += 1ll * (lr - ll + 1) * (rr - rl + 1);
// printf("* [%d %d] [%d %d]\n", ll, lr, rl, rr);
}
}
printf("%lld\n", ans);
return 0;
}
标签：rr,852,int,Moscow,Codeforces,cnt1,ans,端点,ll From： https://www.cnblogs.com/acmLLF/p/17121957.html