题目大意

给定一个序列，多次询问区间 $[l, r]$ 内所有子序列的最小值之和。

算法分析

核心思路：贡献法

考虑每个元素 $a_i$ 对答案的贡献：对于包含 $a_i$ 的子序列，只有当 $a_i$ 是这个子序列的最小值时，它才会为答案贡献 $a_i$ 的值。

对于元素 $a_i$，在区间 $[L, R]$ 中，它能作为最小值的子序列数量等于：

• 在 $a_i$ 左边且值大于 $a_i$ 的连续元素个数 + 1（向左扩展）
• 在 $a_i$ 右边且值大于 $a_i$ 的连续元素个数 + 1（向右扩展）

这两部分的乘积就是包含 $a_i$ 且 $a_i$ 是最小值的子序列数量。

预处理

1. 单调栈求控制区间

   • 对每个 $a_i$，找到左边第一个比它小的位置 $l_i$
   • 找到右边第一个比它小的位置 $r_i$
   • 这样 $a_i$ 作为最小值控制的区间就是 $(l_i, r_i)$

2. 计算贡献

   • 对于元素 $a_i$，在它控制的区间 $(l_i, r_i)$ 内：
     • 左端点可以在 $(l_i, i]$ 中选择，共 $(i - l_i)$ 种选择
     • 右端点可以在 $[i, r_i)$ 中选择，共 $(r_i - i)$ 种选择
   • 因此 $a_i$ 作为最小值的子序列数量为 $(i - l_i) \times (r_i - i)$

回答查询

对于查询 $[L, R]$，只有那些控制区间与 $[L, R]$ 有交集的 $a_i$ 才会产生贡献。

具体来说，$a_i$ 对查询 $[L, R]$ 有贡献当且仅当：

• $L \leq i \leq R$（$a_i$ 在查询区间内）
• $l_i < L$ 且 $r_i > R$（$a_i$ 在 $[L, R]$ 内是最小值）

贡献值为：$a_i \times (i - L + 1) \times (R - i + 1)$

复杂度分析

• 预处理：$O(n)$
• 每次查询：理论上可以做到 $O(\log n)$ 或 $O(1)$
• 总复杂度：$O(n + q)$ 或 $O(n + q \log n)$

代码框架（伪代码）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int n, q;
vector<int> a;
int A, B, C, P;
ll lastAns = 0;

inline int rnd() {
    return A = (A * B + (C ^ (int)(lastAns & 0x7fffffffLL)) % P) % P;
}

int main() {
    cin >> n >> q;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> A >> B >> C >> P;
    
    // 单调栈预处理左右边界
    vector<int> left(n + 2), right(n + 2);
    stack<int> st;
    
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        left[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }
    
    while (!st.empty()) st.pop();
    
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] > a[i]) {
            st.pop();
        }
        right[i] = st.empty() ? n + 1 : st.top();
        st.push(i);
    }
    
    // 计算总答案
    ll total = 0;
    for (int i = 0; i < q; i++) {
        int l = rnd() % n + 1;
        int r = rnd() % n + 1;
        if (l > r) swap(l, r);
        
        // 计算区间 [l, r] 的答案
        ll ans = 0;
        for (int j = l; j <= r; j++) {
            if (left[j] < l && right[j] > r) {
                ans = (ans + (ll)a[j] * (j - l + 1) % MOD * (r - j + 1) % MOD) % MOD;
            }
        }
        lastAns = ans;
        total = (total + ans) % MOD;
    }
    
    cout << (total + MOD) % MOD << endl;
    return 0;
}

优化提示

上述直接枚举的解法对于 $q$ 很大时可能超时，实际需要：

• 使用更高效的数据结构（如线段树、ST表）
• 离线处理查询
• 利用前缀和等技巧加速计算

关键点

1. 贡献思想：将问题转化为每个元素作为最小值时的贡献
2. 单调栈：高效求出每个元素作为最小值的影响范围
3. 区间交集：判断元素在查询区间内是否仍为最小值

这个题目很好地结合了数据结构与动态规划思想，是练习贡献法和单调栈的经典题目。