题解 P2717 【寒假作业】

ghj1222 · 2019-02-09 17:14:09 · 题解

非常简单的cdq分治

先把所有数-=k，转化为平均数>=0的区间数量

也就是区间和>=0的区间数量

对于区间[l, r]内部所有区间的贡献，令区间中点为mid，先计算[l, mid]和[mid + 1, r]的所有贡献，然后再计算[l, r]内所有跨过区间中点mid的区间贡献就行

跨过中点的区间一定是i\in[l,mid]的一段[i, mid]和j\in[mid + 1, r]的一段[mid + 1, j]组成，我们前面求后缀和后面求前缀和把所有上述区间和搞出来，然后分别排序双指针扫一遍就可以统计答案了

有前缀和转化为逆序对的做法，实质其实一样，都是cdq分治

#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, a[100010];
int tmp[100010];

long long cdq(int l, int r)
{
    if (l == r) return a[l] >= 0;
    int mid = (l + r) / 2;
    long long ans = cdq(l, mid) + cdq(mid + 1, r);
    tmp[mid] = a[mid];
    tmp[mid + 1] = a[mid + 1];
    for (int i = mid - 1; i >= l; i--)
        tmp[i] = tmp[i + 1] + a[i];
    for (int i = mid + 2; i <= r; i++)
        tmp[i] = tmp[i - 1] + a[i];
    sort(tmp + l, tmp + mid + 1);
    sort(tmp + mid + 1, tmp + r + 1);
    for (int i = l, j = r; i <= mid; i++)
    {
        while (j > mid && tmp[i] + tmp[j] >= 0) j--;
        ans += r - j;
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] -= k;
    printf("%lld\n", cdq(1, n));
    return 0;
}