Moscow Gorillas
考虑区间不包含的最小的数
对于1 不包含1的区间都可取
对于2 在包含1的基础上不包含2 以此类推
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
vector<int> pos1(n+1),pos2(n+1);
for (int i=1;i<=n;i++){
int x;
cin>>x;
pos1[x]=i;
}
for (int i=1;i<=n;i++){
int x;
cin>>x;
pos2[x]=i;
}
for (int i=1;i<=n;i++){
if (pos2[i]<pos1[i]){
swap(pos1[i],pos2[i]);
}
}
int l=pos1[1],r=pos2[1];
// cout<<l<<" "<<r<<"\n";
ll ans=1LL*(l-1)*l/2+1LL*(n-r)*(1+n-r)/2+1LL*(r-l)*(r-l-1)/2;
for (int i=2;i<=n;i++){
if (pos2[i]>r&&pos1[i]<l){
ans+=1LL*(l-pos1[i])*(pos2[i]-r);
l=pos1[i];
r=pos2[i];
}else if (pos2[i]<l){
ans+=1LL*(l-pos2[i])*(n-r+1);
l=pos1[i];
}else if (pos1[i]>r){
ans+=1LL*(pos1[i]-r)*l;
r=pos2[i];
}
else{
l=min(l,pos1[i]);
r=max(r,pos2[i]);
}
}
cout<<ans+1;
return 0;
}