https://codeforces.com/contest/1793/problem/D
解题思路
依次找出 MEX = 1..n+1的序列数量就能得解。
MEX = n+1 只有全序列这一种情况。
MEX = 1时，找出两个序列中1的位置，较小位置左边的元素构成的子序列，较大位置右边的元素构成的子序列，以及两个位置中间的元素构成的子序列都满足。
MEX = i (i∈2...n) 时，找出两个序列同时包含 1~i 的最短子序列，记为S。如果 i+1 在S中，则无解。否则，根据 i+1 在两个序列中的位置，计算可能的序列组合数。下一轮计算两个序列同时包含 1~i+1 的最短子序列的范围，可以根据S的范围以及i+1的位置进行推导。
/* https://codeforces.com/problemset/problem/1793/D */ #include <bits/stdc++.h> using namespace std; #define N 200001 int n, p[N], q[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); while (cin >> n) { int tmp; for (int i = 1; i <= n; i++) { cin >> tmp; p[tmp] = i; } for (int i = 1; i <= n; i++) { cin >> tmp; q[tmp] = i; } int64_t ans = 1, l, r, prel, prer; prel = l = min(p[1], q[1]); prer = r = max(p[1], q[1]); ans += (l-1)*l/2; ans += (n-r+1)*(n-r)/2; ans += (r-l)*(r-l-1)/2; for (int i = 1; i < n; i++) { l = min(p[i], q[i]); r = max(p[i], q[i]); l = min(l, prel), r = max(r, prer); if ((l <= p[i+1] && p[i+1] <= r) || (l <= q[i+1] && q[i+1] <= r)) { prel = l, prer = r; continue; } int ml = 1, mr = n; int left = min(p[i+1], q[i+1]); int right = max(p[i+1], q[i+1]); ml = left+1 <= l ? left+1 : ml; ml = right+1 <= l ? right+1 : ml; mr = right-1 >= r ? right-1 : mr; mr = left-1 >= r ? left-1 : mr; int64_t nl = l - ml, nr = mr - r; // cout << "..." << i << " [" << l << "," << r << "] " << nl * nr + nl + nr + 1 << endl; ans += nl * nr + nl + nr + 1; prel = l, prer = r; } cout << ans << endl; } return 0; }