Abstract

传送门
给出一个序列，要求我们找出平均值大于 m 的子段的数量。这题和逆序对还有些关系呢。

Idea

很容易想到，我们要对原序列进行以下预处理：a[i] -= m ，这样一来，问题转变为找和值大于 0 的子段,那么我们再对原序列做一次前缀和，接下来，对于区间 [l,r] ，若 a[r] - a[l-1] > 0,则这个区间形成一个合法子段，等等，这不就是在找顺序对吗？把这个序列倒过来就是找逆序对的模板题了！

顺便解释一下求逆序对的方法，直接看代码注释吧。

Code

#include <bits/stdc++.h>
using namespace std;
const int MOD = 92084931;
int n, m;
int nums[10000000];
int b[10000000];
int ans;
void msort(int l, int r)
{
    if (l == r)
    {
        return;
    }
    // 分成两半，依次排好序
    int mid = l + r >> 1;
    // 左右两部分各自产生的逆序对在排序时已经被计算
    msort(l, mid);
    msort(mid + 1, r);
    // 接下来把这排好的两部分合并
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
    {
        if (nums[i] <= nums[j])
        {
            b[k++] = nums[i++];
        }
        else // 计算右边区间的数产生了多少逆序对
        {
            // mid+1-i 是右边区间的每一个数产生的贡献
            b[k++] = nums[j++], ans += (mid + 1 - i) % MOD;
            ans %= MOD;
        }
    }
    // 把剩下的数也加到序列里面
    while (i <= mid)
    {
        b[k++] = nums[i++];
    }
    while (j <= r)
    {
        b[k++] = nums[j++];
    }
    for (int i = l; i < r + 1; i++)
    {
        nums[i] = b[i];
    }
    return;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n; i++)
    {
        int p;
        scanf("%d ", &p);
        p -= m;
        nums[i] = p + nums[i - 1];
        if (nums[i] > 0)
        {
            ans++;
            ans %= MOD;
        }
    }
    scanf("%d", &nums[n]);
    nums[n] -= m;
    nums[n] += nums[n - 1];
    if (nums[n] > 0)
    {
        ans++;
        ans %= MOD;
    }
    reverse(nums + 1, nums + 1 + n);
    msort(1, n);
    cout << ans;
    return 0;
}