Codeforces Round #852 (Div. 2) D - Moscow Gorillas
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; }
浙公網安備 33010602011771號