洛谷P2804题解：树状数组与离散化技术的完美结合

一、问题描述

给定一个整数序列，求有多少个连续子序列的平均数等于给定的目标值m。这个问题可以转化为统计前缀和满足特定条件的区间数量。

二、算法核心思想

1. 前缀和转换：将平均数问题转化为前缀和问题

2. 离散化处理：处理大范围和负数情况

3. 树状数组应用：高效统计满足条件的区间数量

三、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 2, 0) {}
    
    void update(int idx) {
        for (; idx < tree.size(); idx += idx & -idx)
            tree[idx]++;
    }
    
    int query(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += tree[idx];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    if (n <= 0) {  // 处理非法输入
        cout << 0 << endl;
        return 0;
    }

    vector<ll> a(n + 1), sum(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i] - m; // 关键转换：sum[i] = (a[1]+...+a[i]) - i*m
    }

    // 离散化处理（兼容负数和大数）
    vector<ll> discrete = sum;
    sort(discrete.begin(), discrete.end());
    discrete.erase(unique(discrete.begin(), discrete.end()), discrete.end());

    auto get_rank = [&](ll val) {
        return lower_bound(discrete.begin(), discrete.end(), val) - discrete.begin() + 1;
    };

    FenwickTree ft(discrete.size());
    ll ans = 0;
    ft.update(get_rank(sum[0]));  // 初始前缀和0必须计入

    for (int i = 1; i <= n; ++i) {
        int rank = get_rank(sum[i]);
        ans += ft.query(rank - 1);  // 统计比当前小的数
        ft.update(rank);
    }

    cout << ans % 92084931 << endl;
    return 0;
}

四、算法分步解析

1. 前缀和转换：

• 将原问题转换为寻找sum[j] - sum[i] ≥ 0的区间

• 关键公式：sum[i] = (a[1]+...+a[i]) - i*m

2. 离散化处理：

• 对前缀和数组进行排序去重

• 建立值到排名的映射关系

• 解决大数值范围和负数问题

3. 树状数组操作：

• 初始化树状数组

• 动态维护和查询前缀和排名

• 统计满足条件的区间数量

五、常见误区与调试技巧

1. 忘记初始化树状数组

2. 离散化处理不完整导致数组越界

3. 前缀和转换公式错误

4. 边界条件处理不当