维护两个单调递减的栈，当i加进栈，位置x的数弹出的时候，在另一个栈中找到和这个数一样大的数，计算贡献（x-靠右左端点）*（i-x）。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #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<r) { int mid=(l+r)>>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<r) { int mid=(l+r)>>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 ",ans); return 0; }