题意:有两个排列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);
}