房产网站建设推广,图片设计软件免费版,淮安网站建设淮安网站制作,企业网站营销典型案例Problem - D - Codeforces 在冬天#xff0c;莫斯科动物园的居民非常无聊#xff0c;尤其是大猩猩。你决定娱乐他们#xff0c;带了一个长度为n的排列p到动物园。长度为n的排列是由n个从1到n的不同整数以任意顺序组成的数组。例如#xff0c;[2,3,1,5,4]是一个排列#xf…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, Pl1p]) MEX([a,91a])。数列的MEX是数列中缺少的最小正整数。例如MEX([1,3]) 2MEX([5]) 1, MEX([3,1,2,6]) 4。你不想拿自己的健康冒险所以你也不敢拒绝大猩猩。输入第一行包含一个整数n (1 n2.105)-排列长度。第二行包含n个整数p1 P2。Pn (1 pi Sn)-排列p的元素。第三行包含n个整数q1,92an (1 gi Sn)-排列q的元素。输出打印一个整数-合适的对l和r的数量。
Examples
input
Copy 3
1 3 2
2 1 3
output
Copy
2input
Copy 7
7 3 6 2 1 5 4
6 7 2 5 3 1 4
output
Copy
16input
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的位置xy, x,y要么同时出现在【1,L-1】一侧要么同时出现在【R1,n】一侧要么一边在【1,L-1】一边在【R1,n】。
成立的情况只有三种
1.都在L的左边 (L-y)*(n-R1)
2.都在R的右边 L*(x-R)
3.x在L左边,y在R右边 (L-x)*(y-R)
随着MEX()增大,L,R区间会逐渐增大,或不变,所以要不断更新,
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
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 (n1)*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 - R1);}else if(x R){ans L*(x - R);}else if(x Ly 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();}
}
