题目链接：https://www.luogu.com.cn/problem/CF689D
解题思路：因为
[max_{i=l}^{r} a_i
]
随 (r) 单调递增；
[min_{i=l}^{r} b_i
]
随 (r) 单调递减。
所以我们可以枚举 (l)，二分
[max_{i=l}^{r} a_i = min_{i=l}^{r} b_i
]
对应的 (r) 的左右边界。
区间最值可以用 ST表 维护。
示例代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
int n, a[maxn], b[maxn], fa[maxn][20], fb[maxn][20];
void init() {
for (int j = 0; (1<<j) <= n; j ++) {
for (int i = 1; i+(1<<j)-1 <= n; i ++) {
if (j == 0) fa[i][j] = a[i], fb[i][j] = b[i];
else fa[i][j] = max(fa[i][j-1], fa[i+(1<<(j-1))][j-1]), fb[i][j] = min(fb[i][j-1], fb[i+(1<<(j-1))][j-1]);
}
}
}
int calmax(int l, int r) {
int m = r - l + 1;
int j = log2(m);
return max(fa[l][j], fa[r-(1<<j)+1][j]);
}
int calmin(int l, int r) {
int m = r - l + 1;
int j = log2(m);
return min(fb[l][j], fb[r-(1<<j)+1][j]);
}
int get_first(int l) {
int L = l, R = n, res = -1;
while (L <= R) {
int mid = (L + R) / 2;
int v1 = calmax(l, mid), v2 = calmin(l, mid);
if (v1 >= v2) {
R = mid - 1;
if (v1 == v2) res = mid;
}
else L = mid + 1;
}
return res;
}
int get_last(int l) {
int L = l, R = n, res = -1;
while (L <= R) {
int mid = (L + R) / 2;
int v1 = calmax(l, mid), v2 = calmin(l, mid);
if (v1 <= v2) {
L = mid + 1;
if (v1 == v2) res = mid;
}
else R = mid - 1;
}
return res;
}
long long ans;
void solve(int l) {
int p1 = get_first(l), p2 = get_last(l);
if (p1 != -1) ans += p2 - p1 + 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", a+i);
for (int i = 1; i <= n; i ++) scanf("%d", b+i);
init();
for (int l = 1; l <= n; l ++) solve(l);
printf("%lld
", ans);
return 0;
}