题目描述
难度分:1800
输入n(1≤n≤2×105)和两个1~n的排列p和q。
定义mex(a)为不在a中的最小正整数。注意是正整数。定义A[i..j]表示A中下标从i到j的子数组。
输出有多少个下标对(i,j),满足i≤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的最小子数组的左端点l1和右端点 r1。维护包含q中1,2,…,v−1的最小子数组的左端点l2和右端点r2。
设pos1[v]为v在p中的下标,pos2[v]为v在q中的下标。(下标从0开始)对于不含v的方案数:
-
设l=−1,如果pos1[v]<l1,那么l=pos1[v],如果pos2[v]<l2,那么l和pos2[v]取max。
-
设r=n,如果pos1[v]>r1,那么r=pos1[v],如果pos2[v]>r2,那么r和pos2[v]取min。
子数组的左端点可以从l+1到min(l1,l2),有max(min(l1,l2)−l,0)个。
子数组的右端点可以从max(r1,r2)到r−1,有max(r−max(r1,r2),0)个。方案数为max(min(l1,l2)−l,0)×max(r−max(r1,r2),0),把所有v的贡献都累加起来就是答案。
复杂度分析
时间复杂度
从v=2开始遍历到n,每次计算包含[1,v−1]不包含v的贡献时间复杂度为O(1)。因此,整个算法的时间复杂度为O(n)。
空间复杂度
在整个过程中开辟了pos1数组和pos2数组分别用于存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;
}