维护两个单调递减的栈，当i加进栈，位置x的数弹出的时候，在另一个栈中找到和这个数一样大的数，计算贡献（x-靠右左端点）*（i-x）。

#include
      
       #include
       
        #include
        
         #include
         
           #include
          
           #define ll long long using namespace std;const int maxn=500010,inf=1e9;int n,m,x,y,z,tot,topa,topb;int a[maxn],b[maxn],sta[maxn],stb[maxn];ll ans;void read(int &k){    int f=1;k=0;char c=getchar();    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();    k*=f;}int main(){    read(n);    for(int i=1;i<=n;i++)read(a[i]);    for(int i=1;i<=n;i++)read(b[i]);    a[++n]=inf;b[n]=inf-1;    for(int i=1;i<=n;i++)    {        for(;topa&&a[sta[topa]]<=a[i];topa--)        {            if(!topb)continue;            int l=1,r=topb;            while(l
           
            >1; if(b[stb[mid]]<=a[sta[topa]])r=mid; else l=mid+1; } int x=l;if(b[stb[x]]!=a[sta[topa]])continue; ans+=1ll*max(0,min(stb[x],sta[topa])-max(stb[x-1],sta[topa-1]))*(i-max(stb[x],sta[topa])); } for(;topb&&b[stb[topb]]<=b[i];topb--) { if(!topa)continue; int l=1,r=topa; while(l
            
             >1; if(a[sta[mid]]<=b[stb[topb]])r=mid; else l=mid+1; } int x=l;if(a[sta[x]]!=b[stb[topb]])continue; ans+=1ll*max(0,min(sta[x],stb[topb])-max(sta[x-1],stb[topb-1]))*(i-max(sta[x],stb[topb])); } sta[++topa]=stb[++topb]=i; } printf("%lld\n",ans); return 0;}