类似hdu5289,但是二分更复杂。本题枚举左端点，右端点是一个区间，需要二分找到区间的左端点和右端点（自己手动模拟一次），然后区间长度就是结果增加的次数
另外结果开long long 保存
/** 二分法，枚举左端点，向右寻找第一个最大值不等于最小值的端点 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 200050 int a[maxn],b[maxn],mx[maxn][30],mi[maxn][30],n; long long ans; void ST(){ for(int i=1;i<=n;i++) mx[i][0]=a[i],mi[i][0]=b[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++){ mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } } int query1(int L,int R){ int k=log2(R-L+1); return max(mx[L][k],mx[R-(1<<k)+1][k]); } int query2(int L,int R){ int k=log2(R-L+1); return min(mi[L][k],mi[R-(1<<k)+1][k]); } int main(){ cin >> n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); ans=0;ST(); for(int i=1;i<=n;i++){ int l=i,r=n,r1=-1,r2=-1,tmp1,tmp2; while(l<=r){//先找左端点 int mid=l+r>>1; tmp1=query1(i,mid); tmp2=query2(i,mid); if(tmp1<tmp2) l=mid+1;//左端点不够右 else if(tmp1>tmp2) r=mid-1;//左端点右过头了 else r1=mid,r=mid-1;//再往左找 } l=i,r=n; while(l<=r){ int mid=l+r>>1; tmp1=query1(i,mid); tmp2=query2(i,mid); if(tmp1<tmp2) l=mid+1;//右端点不够右 else if(tmp1>tmp2) r=mid-1;//右端点右过头了 else r2=mid,l=mid+1;//再往右找 } if(r1==-1 || r2==-1) continue; ans+=r2-r1+1; } printf("%lld ",ans); return 0; }