思路

首先看到 $\max\limits^r_{i=l}a_i$ 和 $\min\limits^r_{i=l}b_i$，我们很容易想到 ST 表来优化区间最大/最小值查询，不会 ST 表的来这里。

但是光有 ST 表的时间复杂度仍为 $O(n^2)$，不符合题目 $n \leq 2\times10^5$ 的要求，于是我们考虑优化。

不难想到，如果左端点 $l$ 固定，那么 $\max\limits^{i}_{k=l}a_k$ 和 $\min\limits^{i}_{k=l}a_k$ 一定单调不降/不增，此时右端点 $r$ 的取值范围一定是连续的，于是我们可以确定以任意一个 $l$ 作为左端点时的满足条件的 $r$ 的个数。

所以我们只需要求每一个 $r$ 的最大/最小值。

看到这句话，我们不难想到二分搜索，于是可以用二分搜索+ ST 表 AC 这道题。

总复杂度 $O(n\log n)$，通过。

如果看不懂逻辑可以参考代码理解一下。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f1[200100][30],f2[200100][30],sum;//f1代表a,f2代表b
int qmax(int l,int r){//ST表取a的(l,r)中最大值
    if(l == r) return f1[l][0];
	int k = log2(r - l + 1);//也可以预处理
	return max(f1[l][k],f1[r - (1 << k) + 1][k]);
}
int qmin(int l,int r){//ST表取b的(l,r)中最小值
    if(l == r) return f2[l][0];
	int k = log2(r - l + 1);//同上
	return min(f2[l][k],f2[r - (1 << k) + 1][k]);
}
int ql(int i){//二分左端点
	int l = i,r = n;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(qmax(i,mid) < qmin(i,mid)) l = mid + 1;//如果太小就增加
		else r = mid - 1;//否则减小
	}
	if(l <= n && qmax(i,l) == qmin(i,l)) return l;//注意特判
	return 0;
}
int qr(int i){//二分右端点，同上
	int l = i,r = n;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(qmax(i,mid) > qmin(i,mid)) r = mid - 1;
		else l = mid + 1;
	}
	if(r > 0 && qmax(i,r) == qmin(i,r)) return r;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>f1[i][0];
	}
	for(int i = 1;i <= n;i++){
		cin>>f2[i][0];
	}
	for(int j = 1;j <= 21;j++){//预处理ST表
		for(int i = 1;i + (1 << j) - 1 <= n;i++){
			f1[i][j] = max(f1[i][j - 1],f1[i + (1 << (j - 1))][j - 1]);
		}
	}
    for(int j = 1;j <= 21;j++){//同上
		for(int i = 1;i + (1 << j) - 1 <= n;i++){
			f2[i][j] = min(f2[i][j - 1],f2[i + (1 << (j - 1))][j - 1]);
		}
	}
	for(int i = 1;i <= n;i++){
		int l = ql(i),r = qr(i);//二分搜索
		if(l == 0) continue;//满足特判会退出
		if(r == 0) continue;
		if(l > r) swap(l,r);//保险
		sum += (r - l + 1);
	}
	cout<<sum;
	return 0;
}