P2717题解

题目传送门

前言

感谢@HwH和@chenyilei同学提供的帮助！

应该是本题最优雅、简洁易懂的题解。

~~尤菈：对，就是要优雅！~~

嗯嗯，那我们开始！

解析

首先我们看到这个题说的平均数不小于$k$,应该很容易想到将每个数都减去$k$,然后只要考虑大于零即可。

既然是大于零，一个正数除以一个正数还是正数，就不必去除了，只要考虑区间和大于零。

所以为了提高效率我们很显然要用到一个前缀和优化。

然后考虑如何找出有多少段区间和大于零即为答案。

考虑枚举右端点。

容易发现，对于每一个右端点$i$，他前面所有$sum[j]$小于等于$sum[i]$，都可以组成一段区间和大于等于0的连续子序列，也就是题目中所说的平均数$\geq k$的连续子序列。同时，别忘了如果这个$sum[i]$本身$\geq 0$，那么序列$1\sim k$也是一段平均数$\geq k$的连续子序列，此时应该$++ans$。

枚举右端点计算每个右端点对答案的贡献，加和即可。

那么，如何求一个右端点$i$前面所有$sum[j]$小于等于$sum[i]$的$j$有几个呢？

我们可以将$sum[i]$逐个加入，每一个$sum[i]$加入时，他前面有多少小于等于$sum[i]$的，那这个$sum[i]$对于答案的贡献，也就是右端点$i$前面所有$sum[j]$小于等于$sum[i]$的$j$的数量，就是多少。(想想为什么，虽然很明显)

嗯，思路就是如此简单，那么如何实现呢？

emm……我想想……

不停加入数，然后查询它是目前的第几名……

嗯！我想到了！一定是优雅的平衡树！

对，我们在这里为了优雅，尽量使main函数简洁易懂，使用易于封装漂亮的平衡树实现。

我在这里使用的是优雅的FHQ-Treap。

~~尤菈屡屡探头~~

代码

#include <bits/stdc++.h>
#define INF 999999999
#define arand() rand() % 114514
#define mrg() rot = merge(X, Y)

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void write(const long long &x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    char f[100];
    long long tmp = x;
    if (tmp < 0)
    {
        tmp = -tmp;
        putchar('-');
    }
    long long s = 0;
    while (tmp > 0)
    {
        f[s++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (s > 0)
    {
        putchar(f[--s]);
    }
}

const long long maxN = 1000090;
long long totN;
long long totK;
long long nums[maxN];
long long sum[maxN];
priority_queue<long long> Q;

struct Node
{
    long long lch, rch;
    long long val, siz;
    long long rnd;
} nodes[maxN];

long long X, Y, Z;
long long rot;
long long cnt;
long long totANS;

void update(long long nowX)
{
    nodes[nowX].siz = nodes[nodes[nowX].lch].siz + nodes[nodes[nowX].rch].siz + 1;
}

long long merge(long long Atree, long long Btree)
{
    if ((!Atree) || (!Btree))
    {
        return Atree + Btree;
    }
    else if (nodes[Atree].rnd < nodes[Btree].rnd)
    {
        nodes[Atree].rch = merge(nodes[Atree].rch, Btree);
        update(Atree);
        return Atree;
    }
    else
    {
        nodes[Btree].lch = merge(Atree, nodes[Btree].lch);
        update(Btree);
        return Btree;
    }
}

void split(long long splitX, long long K, long long &Xtree, long long &Ytree)
{
    if (!splitX)
    {
        Xtree = Ytree = 0;
        return;
    }
    else
    {
        if (nodes[splitX].val <= K)
        {
            Xtree = splitX;
            split(nodes[splitX].rch, K, nodes[splitX].rch, Ytree);
        }
        else
        {
            Ytree = splitX;
            split(nodes[splitX].lch, K, Xtree, nodes[splitX].lch);
        }
        update(splitX);
    }
}

void del(long long delX)
{
    split(rot, delX, X, Z);
    split(X, delX - 1, X, Y);
    Y = merge(nodes[Y].lch, nodes[Y].rch);
    rot = merge(merge(X, Y), Z);
}

void insert(long long nowX)
{
    split(rot, nowX, X, Y);
    ++cnt;
    nodes[cnt].lch = nodes[cnt].rch = 0;
    nodes[cnt].val = nowX;
    nodes[cnt].siz = 1;
    nodes[cnt].rnd = arand();
    rot = merge(merge(X, cnt), Y);
}

long long thK(long long nowX)
{
    split(rot, nowX , X, Y);
    return nodes[X].siz - 1;
}

int main()
{
    totN = read();
    totK = read();
    for (long long i = 1; i <= totN; ++i)
    {
        nums[i] = read() - totK;
        sum[i] = nums[i] + sum[i - 1];
    }
    for (int i = 1; i <= totN; ++i)
    {
        insert(sum[i]);
        totANS += thK(sum[i]) ;
        mrg();
        if (sum[i] >= 0)
        {
            ++totANS;
        }
    }
    write(totANS);
    return 0;
} //Thomitics Code