当前位置: 首页 > 工具软件 > Gorillas > 使用案例 >

cf 852 D Moscow Gorillas

申黎明
2023-12-01

题意:有两个排列P和Q,求符合MEX([pl,pl+1,…,pr])=MEX([ql,ql+1,…,qr])的(l,r)对数。

MEX: 该区间内最小的不能被取到的数(从1开始)。

思路:应该去探求MEX的性质。

例如:MEX=2的区间,应满足两个条件。

                1. 该区间包含1 

                2.该区间不包含2       

          MEX=3的区间应满足:

                1.该区间包含1,2

                2.该区间不包含3

因此,我们可以发现,MEX=2的区间与MEX=3的区间之间有一定联系。

满足MEX=2的最大区间,L或者R必定与2相邻。那么,这个区间将2包括之后,如果3不在该区间内,那么这个区间就是满足MEX=3的最小区间。

4 3 5 2 1

以该数列为例,MEX=2的最大区间为【5,5】,那么【4,5】就是最小的MEX=3的区间。

这样我们就可以确定 MEX=i  与 MEX=i+1 存在递推关系。

我们定义pos[i]表示i所在的位置,那么MEX=i+1 的最小区间为[min(pos[1],pos[2]...pos[i]),max(pos[1],pos[2]...pos[i])] 

然后你要判断 pos[i+1]是否在该区间内,如果pos[i+1]在该区间内,那么MEX=i+1是没有合法区间的。如果不在该区间内,那么可以根据pos[i+1] 调整MEX=i+1的区间,然后计算合法的 [l,r] 对数。

#include<bits/stdc++.h>
#define N 203500
using namespace std;
long long n,a[N],b[N],posa[N],posb[N],la,ra,lb,rb,pa,pb,qa,qb;
long long ans;
int main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		posa[a[i]]=i;
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
		posb[b[i]]=i;
	}
	la=n;ra=1;
	lb=n;rb=1;
	ans+=(min(posa[1],posb[1])-1)*(min(posa[1],posb[1]))/2;  
	ans+=(n-max(posa[1],posb[1])+1)*(n-max(posa[1],posb[1]))/2;
	ans+=(max(posa[1],posb[1])-min(posa[1],posb[1])-1)*(max(posa[1],posb[1])-min(posa[1],posb[1]))/2;
	for (int i=1;i<n;i++)
	{
		la=min(la,posa[i]);lb=min(lb,posb[i]);
		ra=max(ra,posa[i]);rb=max(rb,posb[i]);
		if (posa[i+1]<la) {pa=posa[i+1]+1;qa=n;}
		if (posa[i+1]>=la && posa[i+1]<=ra) {continue;}
		if (posa[i+1]>ra) {pa=1;qa=posa[i+1]-1;}
		if (posb[i+1]<lb) {pb=posb[i+1]+1;qb=n;}
		if (posb[i+1]>=lb && posb[i+1]<=rb) {continue;}
		if (posb[i+1]>rb) {pb=1;qb=posb[i+1]-1;}
		ans+=(max(0LL,min(la,lb)-max(pa,pb)+1))*(max(0LL,min(qa,qb)-max(ra,rb)+1));
        //la ra lb rb  a,b满足MEX=i+1的最小区间
        //pa qa pb qb  a,b满足MEX=i+1的最大区间
        //计算时肯定要满足最大区间包含最小区间
	}
	ans++;
	printf("%lld\n",ans);
	
	
}

 类似资料:

相关阅读

相关文章

相关问答