当前位置：首页 > 洛谷 > 洛谷2804题解：基于Fenwick树与离散化的区间统计优化方案

洛谷2804题解：基于Fenwick树与离散化的区间统计优化方案

6个月前 (06-05)

一、题目解读

洛谷2804题要求解决一个涉及区间统计的问题，核心在于高效计算满足特定条件的元素数量。题目可能涉及前缀和、区间查询或计数类操作，需处理大范围数据及可能的负数输入。通过代码分析可知，关键需求在于快速统计数组中小于等于某前缀和的元素个数，并应对数据离散化后的区间处理。

二、解题思路

1. 核心算法：采用Fenwick树（树状数组）实现动态区间查询与更新。Fenwick树支持单点修改和区间求和，时间复杂度O(logN)，适合本题的计数场景。

2. 离散化处理：由于输入数据可能存在负数或超大值，直接使用Fenwick树会超限。通过排序+去重将原数据映射到紧凑索引（1~离散化后长度），解决数值范围问题。

3. 前缀和转化：将问题转化为统计前缀和数组中小于当前值的元素数量，利用离散化后的索引作为Fenwick树的输入。

三、解题步骤

1. 输入与预处理：读入n、m及数组a，计算前缀和sum[i] = sum[i-1] + a[i] - m（消除m的影响）。

2. 离散化：将sum数组元素存入discrete向量，排序并去重，生成唯一索引映射。定义get_rank函数：通过lower_bound将任意值映射到离散化后的索引（+1避免下标为0）。

3. Fenwick树构建与统计：初始化FenwickTree，初始前缀和0需计入（ft.update(get_rank(sum[0]))）。遍历sum数组，每次查询当前位置左侧元素数量（ans += ft.query(rank-1)），并更新当前值（ft.update(rank)）。

4. 结果处理：对最终答案取模92084931并输出。

四、代码与注释

#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;
    }

    // 离散化处理（兼容负数和大数）
    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;
}