一、题意回顾（核心公式）

给定数组 $a$ 和 $b$，对所有子区间 $[l,r]$：

1. 要求数组 $z$ 的前缀最大值和 $a$ 完全相同：

$$\forall i\in[l,r],\quad \max(a_l,\dots,a_i)=\max(z_l,\dots,z_i) $$

2. $f([l,r])$ 表示满足条件时，最多能让多少位 $z_i=b_i$。
3. 求所有子区间的 $f$ 值之和：

$$\boldsymbol{ans}=\sum_{l=1}^n\sum_{r=l}^n f([l,r]) $$

---

二、核心结论（算法灵魂）

这道题的终极突破口：贡献法 我们不枚举区间 $[l,r]$，而是计算每个位置 $i$ 能对多少个区间贡献 $1$。

最终答案 = 所有位置 $i$ 的总贡献数。

关键判定（位置 $i$ 能生效的条件）

对区间 $[l,r]$，位置 $i$ 能让 $z_i=b_i$ 的充要条件：

$$\boldsymbol{\max(a_l,\dots,a_i) \ge \max(a_i,b_i)} $$

满足这个条件，$i$ 就能贡献 $1$。

---

三、完整算法步骤

1. 统计合法贡献

对每个下标 $i$：

1. 若 $a[i]=b[i]$：所有区间都包含 $i$ 并生效 总贡献 = 子区间总数：$$cnt = \frac{n(n+1)}{2}$$
2. 若 $a[i]\neq b[i]$： 二分找到最大的左边界 $L$，使得$$\max(a[L..i]) \ge \max(a[i],b[i])$$ 该 $i$ 的总贡献：$$cnt = L \times (n-i)$$

2. 数据结构优化

• 用稀疏表（Sparse Table） 预处理数组 $a$
• 实现 $O(1)$ 区间最大值查询
• 二分 $O(\log n)$ 找左边界

总复杂度：$O(n\log n)$，完美通过 $n\le 2\times 10^5$。

---

四、标程代码逐行详解

1. 稀疏表模板（区间最大值查询）

struct SparseTable {
    int n, logn;
    vector<vector<int>> st;  // 稀疏表本体
    vector<int> lg;          // 预处理log2值
    function<int(int, int)> op; // 操作：max

    SparseTable(vector<int>& a, function<int(int, int)> op) : op(op) {
        n = a.size();
        logn = __lg(n) + 2;
        st.assign(logn, vector<int>(n));
        lg.resize(n+1);
        
        // 预处理log值
        for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
        
        // 初始化：2^0层
        for(int i=0;i<n;i++) st[0][i]=a[i];
        
        // 构建稀疏表
        for(int k=1;k<logn;k++)
            for(int i=0;i+(1<<k)<=n;i++)
                st[k][i]=op(st[k-1][i], st[k-1][i+(1<<(k-1))]);
    }

    // 查询 [l, r) 区间最大值
    int query(int l,int r){
        int len=r-l;
        int k=lg[len];
        return op(st[k][l], st[k][r-(1<<k)]);
    }
};

---

2. 主逻辑（核心计算）

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n), b(n);
        for (int& x : a) cin >> x;
        for (int& x : b) cin >> x;

        // 构建a的区间最大值稀疏表
        SparseTable sq(a, [](int x, int y) { return max(x, y); });
        ll sol = 0;

        for (int i = 0; i < n; i++) {
            // 情况1：a[i]==b[i]，所有区间都生效
            if (a[i] == b[i]) {
                sol += (1LL * n * n + n) / 2;
                continue;
            }

            // 情况2：二分找最大的L
            int lo = -1, hi = i;
            while (lo + 1 < hi) {
                int mid = (lo + hi) / 2;
                // 核心条件：区间max >= max(a[i],b[i])
                if (sq.query(mid, i) >= max(a[i], b[i])) 
                    lo = mid;
                else 
                    hi = mid;
            }
            lo++;
            // 累加贡献：左边可选数 * 右边可选数
            sol += 1LL * lo * (n - i);
        }
        cout << sol << '\n';
    }
    return 0;
}

---

五、核心公式总结

1. 总子区间数

$$\frac{n(n+1)}{2}$$

2. 位置 $i$ 贡献（不相等时）

$$\text{cnt}[i] = L \times (n-i)$$

3. 最终答案

$$ans=\sum_{i=1}^n \text{cnt}[i]$$

---

六、复杂度说明

• 稀疏表构建：$O(n\log n)$
• 每个位置二分：$O(\log n)$
• 总复杂度：$O(n\log n)$
• 完全适配题目大数据限制：$\sum n \le 2\times 10^5$

---

七、一句话记忆法

贡献法 + 二分 + 区间最大值 = 本题答案 每个位置 $i$ 能生效的区间数 = 合法左端点数量 × 右端点数量。