思路与算法

按右端r离线回答查询。对每个左端l维护A_l=max a[l..r]、B_l=max b[l..r]、P_l=A_lB_l及历史和H_l=∑_{t≤r}max a[l..t]max b[l..t]。加入a_r/b_r时，两个单调栈分别给出需要覆盖赋值的左端后缀区间；线段树支持区间赋A、赋B以及全局H+=P。询问[l,r]取这些左端的H之和。延迟标记将A/B分别保留或赋常量，历史增量表示成pAB+xA+yB+c，组合时把前一个A/B赋值代入后一个多项式。

正确性说明

对固定r，单调栈界定前一个更大值位置，之后的所有左端最大值都会变成当前值，之前不变，故两个覆盖赋值准确。更新后P就是本右端所有子数组的目标值，累加到H使其按右端收集全部子数组。查询时只求左端≥l且≤r的H，历史上未激活的左端P为0，因此恰枚举查询区间内全部子数组。标记多项式包含A、B、AB和常数的所有可能历史贡献，对常量代入封闭；按先旧后新的函数复合推导标记，正确下传。

复杂度

O((n+Q)log n)时间、O(n+Q)空间，含节点全零、查询桶和两个单调栈初始化。

易错点

历史和不能只用当前最大值乘长度。所有乘法、累加及延迟标记都用unsigned long long，自然按2^64取模；输出无符号十进制。赋值标志以0表示未设置，仅因题中排列值均为正才成立。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using U = unsigned long long;
struct Tag {
    U a = 0, b = 0, p = 0, x = 0, y = 0, c = 0;
};
struct Node {
    U A = 0, B = 0, P = 0, H = 0;
    Tag tag;
};
struct Seg {
    int n;
    vector<Node> t;
    Seg(int n) : n(n), t(4 * n) {
    }
    void apply(int u, int l, int r, Tag z) {
        auto &v = t[u];
        U len = r - l + 1;
        v.H += z.p * v.P + z.x * v.A + z.y * v.B + z.c * len;
        if (z.a && z.b)
            v.P = z.a * z.b * len;
        else if (z.a)
            v.P = z.a * v.B;
        else if (z.b)
            v.P = z.b * v.A;
        if (z.a)
            v.A = z.a * len;
        if (z.b)
            v.B = z.b * len;
        auto &a = v.tag;
        if (a.a && a.b)
            a.c += z.p * a.a * a.b;
        else if (a.a)
            a.y += z.p * a.a;
        else if (a.b)
            a.x += z.p * a.b;
        else
            a.p += z.p;
        if (a.a)
            a.c += z.x * a.a;
        else
            a.x += z.x;
        if (a.b)
            a.c += z.y * a.b;
        else
            a.y += z.y;
        a.c += z.c;
        if (z.a)
            a.a = z.a;
        if (z.b)
            a.b = z.b;
    }
    void push(int u, int l, int r) {
        int m = (l + r) / 2;
        apply(2 * u, l, m, t[u].tag);
        apply(2 * u + 1, m + 1, r, t[u].tag);
        t[u].tag = Tag();
    }
    void pull(int u) {
        t[u].A = t[2 * u].A + t[2 * u + 1].A;
        t[u].B = t[2 * u].B + t[2 * u + 1].B;
        t[u].P = t[2 * u].P + t[2 * u + 1].P;
        t[u].H = t[2 * u].H + t[2 * u + 1].H;
    }
    void update(int u, int l, int r, int L, int R, Tag z) {
        if (L <= l && r <= R) {
            apply(u, l, r, z);
            return;
        }
        push(u, l, r);
        int m = (l + r) / 2;
        if (L <= m)
            update(2 * u, l, m, L, R, z);
        if (R > m)
            update(2 * u + 1, m + 1, r, L, R, z);
        pull(u);
    }
    U query(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R)
            return t[u].H;
        push(u, l, r);
        int m = (l + r) / 2;
        U v = 0;
        if (L <= m)
            v += query(2 * u, l, m, L, R);
        if (R > m)
            v += query(2 * u + 1, m + 1, r, L, R);
        return v;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, n;
    cin >> T >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int Q;
    cin >> Q;
    vector<vector<pair<int, int>>> queries(n + 1);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        queries[r].push_back({l, i});
    }
    vector<U> ans(Q);
    Seg tree(n);
    vector<int> sa, sb;
    for (int i = 1; i <= n; i++) {
        while (!sa.empty() && a[sa.back()] < a[i])
            sa.pop_back();
        Tag z;
        z.a = a[i];
        tree.update(1, 1, n, sa.empty() ? 1 : sa.back() + 1, i, z);
        sa.push_back(i);
        while (!sb.empty() && b[sb.back()] < b[i])
            sb.pop_back();
        z = Tag();
        z.b = b[i];
        tree.update(1, 1, n, sb.empty() ? 1 : sb.back() + 1, i, z);
        sb.push_back(i);
        z = Tag();
        z.p = 1;
        tree.apply(1, 1, n, z);
        for (auto q : queries[i])
            ans[q.second] = tree.query(1, 1, n, q.first, i);
    }
    for (U x : ans)
        cout << x << "\n";
}