本文共 2731 字，大约阅读时间需要 9 分钟。

对于给定的数组和查询，我们需要计算满足特定条件的子数组的和。具体来说，每个查询 [l, r] 要求找到所有子数组 [i, j]，其中 l ≤ i < j ≤ r，且 a[i] 是该子数组中的最大值。

方法思路

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
struct Query {
    int l, r, val, id;
    bool operator<(const Query &rhs) const { return id < rhs.id; }
};
vector
      
       
        > q;
void Pre() {
    static int st[MAXN], top = 0;
    for (int i = 1; i <= N; ++i) {
        while (top && a[i] > a[st[top]]) {
            R[st[top--]] = i;
        }
        L[i] = st[top];
        st[++top] = i;
    }
    for (int i = 1; i <= N; ++i) {
        q[R[i]].push_back({L[i] + 1, i - 1, p2, -R[i]});
        q[L[i]].push_back({i + 1, R[i] - 1, p1, -R[i]});
    }
}
void IntAdd(int k, int l, int r, int ql, int qr, int v) {
    if (ql > qr) return;
    if (ql <= l && r <= qr) {
        sum[k] += (r - l + 1) * v;
        f[k] += v;
        return;
    }
    pushdown(k);
    int mid = l + r > 1 ? l + (r - l + 1) / 2 : l;
    if (ql <= mid) {
        IntAdd(ls, l, mid, ql, qr, v);
    }
    if (qr > mid) {
        IntAdd(rs, mid + 1, r, ql, qr, v);
    }
    update(k);
}
LL IntQuery(int k, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return sum[k];
    pushdown(k);
    int mid = l + r > 1 ? l + (r - l + 1) / 2 : l;
    if (ql <= mid) {
        return IntQuery(ls, l, mid, ql, qr);
    } else if (qr <= mid) {
        return IntQuery(rs, mid + 1, r, ql, qr);
    } else {
        return IntQuery(ls, l, mid, ql, qr) + IntQuery(rs, mid + 1, r, ql, qr);
    }
}
int main() {
    N = read();
    M = read();
    p1 = read();
    p2 = read();
    for (int i = 1; i <= N; ++i) {
        a[i] = read();
    }
    Pre();
    Build(1, 0, N + 1);
    for (int i = 1; i <= M; ++i) {
        int a = read(), b = read();
        ans[i] = (b - a) * p1;
        q[a - 1].push_back({a, b, -1, i});
        q[b].push_back({a, b, 1, i});
    }
    for (int i = 0; i <= N; ++i) {
        sort(q[i].begin(), q[i].end());
        for (auto &x : q[i]) {
            if (x.id < 0) {
                IntAdd(1, 0, N + 1, x.l, x.r, x.val);
            } else {
                ans[x.id] += 1LL * x.val * IntQuery(1, 0, N + 1, x.l, x.r);
            }
        }
    }
    for (int i = 1; i <= M; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}
       
      
     
    
   

代码解释

这种方法确保了预处理和查询的高效性，能够处理大规模数据。

转载地址：http://dwrfk.baihongyu.com/