样例 1
输入：
6
1 2 3 2 1 4
6 7 1 2 3 2
输出：
2
备注
1≤n≤10^6，1≤ai,bi≤10^9。
思路：
（1）使用ST表。
ST表（Sparse Table）是一种用于高效处理区间查询的数据结构。它可以在O(1)的时间复杂度内回答某一区间的最值查询（最小值、最大值等）。ST表使用动态规划的思想，通过预处理的方式来快速计算出各个区间的最值。
（2）使用二分。因为此题具有单调性：随着放入数组的数越多，最大值一定非递减。最小值一定非递增。如果固定右端点r，则向左看，最大值从l->r呈阶梯状递增，最小值从l->r呈阶梯状递减，其中一定有交点使最小值=最大值。因为是阶梯状递增和递减，所以交点为横着的一条线段，即l的范围为此线段的范围。
所以每次枚举r，找l的范围并保存在答案中。找l的范围即找max=min，用二分来找。
此题代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, a[N], b[N], mn[N][20], mx[N][20], Lg[N], l, r, mid, ans; void pre() { Lg[1] = 0; for (int i = 2; i <= n; i++) { Lg[i] = Lg[i >> 1] + 1; } } void ST_create() { // 创建ST表 for (int i = 1; i <= n; i++) { mx[i][0] = a[i], mn[i][0] = b[i]; } for (int j = 1; j <= Lg[n]; j++) { for (int i = 1; i <= n - (1 << j) + 1; i++) { mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]); mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]); } } } int ST_qmax(int l, int r) { // ST表求max int k = Lg[r - l + 1]; return max(mx[l][k], mx[r - (1 << k) + 1][k]); } int ST_qmin(int l, int r) { // ST表求min int k = Lg[r - l + 1]; return min(mn[l][k], mn[r - (1 << k) + 1][k]); } int findl(int i) { // l的范围左边界 int l = 1, r = i, mid, ans = 0, minn, maxn; while (l <= r) { mid = (l + r) / 2; maxn = ST_qmax(mid, i), minn = ST_qmin(mid, i); if (maxn <= minn) { ans = mid, r = mid - 1; } else l = mid + 1; } return ans; } int findr(int i) // i为固定的枚举的右边界 { // l的范围右边界 int l = 1, r = i, mid, ans = 0, minn, maxn; while (l <= r) // 二分 { mid = (l + r) / 2; maxn = ST_qmax(mid, i), minn = ST_qmin(mid, i); if (maxn >= minn) { ans = mid, l = mid + 1; } else r = mid - 1; } return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; pre(); ST_create(); for (int i = 1; i <= n; i++) { // 枚举右端点i // 对于每个i，求l的范围findl和findr int j = findl(i); if (j < 1 || j > i) { continue; } int k = findr(i); ans += k - j + 1; } cout << ans; return 0; }
