D. Moscow Gorillas(双指针 + 区间分析)

Problem - D - Codeforces

在冬天，莫斯科动物园的居民非常无聊，尤其是大猩猩。你决定娱乐他们，带了一个长度为n的排列p到动物园。长度为n的排列是由n个从1到n的不同整数以任意顺序组成的数组。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是一个排列(2在数组中出现两次)，[1,3,4也不是一个排列(n3，但4在数组中出现)。大猩猩有自己的长度为n的排列q。他们建议你计算整数l,r (1 r n)对的数量，使得MEX([p1, Pl+1，，p，]) = MEX([a,9+1，，a])。数列的MEX是数列中缺少的最小正整数。例如，MEX([1,3]) = 2，MEX([5]) = 1, MEX([3,1,2,6]) = 4。你不想拿自己的健康冒险，所以你也不敢拒绝大猩猩。输入第一行包含一个整数n (1 <n<2.105)-排列长度。第二行包含n个整数p1 P2。，Pn (1 <pi Sn)-排列p的元素。第三行包含n个整数q1,92，，an (1 <gi Sn)-排列q的元素。输出打印一个整数-合适的对l和r的数量。 

Examples

input

Copy

3

1 3 2

2 1 3

output

Copy

2

input

Copy

7

7 3 6 2 1 5 4

6 7 2 5 3 1 4

output

Copy

16

input

Copy

6

1 2 3 4 5 6

6 5 4 3 2 1

output

Copy

11

题解:

我们假设L,R分别是此时排列p,q1的位置,

那么MEX(1)l,r成立的情况有三种

1.均在L左侧

2.均在R右侧

3.在L,R之间

假设x,y是此时p,q排列的位置

接着考虑MEX = 2的情况。MEX = 2时，说明区间里一定包含1，但不含2，那么2的位置就不能出现在【L,R】之间。设x为序列p中2的位置，y为序列q中2的位置，x<=y, x,y要么同时出现在【1,L-1】一侧，要么同时出现在【R+1,n】一侧，要么一边在【1,L-1】一边在【R+1,n】。

成立的情况只有三种

1.都在L的左边 (L-y)*(n-R+1)

2.都在R的右边 L*(x-R)

3.x在L左边,y在R右边 (L-x)*(y-R)

随着MEX()增大,L,R区间会逐渐增大,或不变,所以要不断更新,

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define int long long
const int N = 6e5 + 10;
int p[N],q[N];
int posp[N];
int posq[N];
int mod = 998244353;
int C(int n)
{return (n+1)*n/2;//区间l == r的情况也要算所以是n*(n-1)/2 + n
}
void solve()
{int n;cin >> n;int ans = 0; for(int i = 1;i <= n;i++){cin >> p[i];posp[p[i]] = i;}for(int i = 1;i <= n;i++){cin >> q[i];posq[q[i]] = i;}int L = posp[1];int R = posq[1];if(L > R)swap(L,R);ans += C(L-1);ans += C(max(0ll,R-L-1));ans += C(n - R);for(int i = 2;i <= n;i++){int x = posp[i];int y = posq[i];if(x > y)swap(x,y);if(y < L){ans += (L - y)*(n - R+1);}else if(x > R){ans += L*(x - R);}else if(x < L&&y > R){ans += (L - x)*(y - R);}L = min(L,x);R = max(R,y);}cout << ans + 1;//+1是整个排列都算一种
}
signed main()
{int t = 1;
//	cin >> t;while(t--){solve();} 
}