题解

选定起点后，不是找一个合适的取盘数，而是要让 $L,L+1,\ldots,R$ 全部合适．所以我们可以先解决：给定起点和盘数，怎样快速判断？

先把平均数比较写成整数比较

设所有盘子共有 $S$ 块点心，取走的 $k$ 盘共有 $x$ 块．要求是

因为 $k$ 和 $n-k$ 都大于 $0$，两边乘上 $k(n-k)$，得到

展开后，两边都有 $-kx$，去掉它们，就是

这样就不需要计算小数了．注意两边的乘积要用 long long．

为了方便处理跨过第 $n$ 盘的情况，把数组复制一遍．原来的第 $s$ 盘开始取 $k$ 盘，在新数组里就是区间 $[s,s+k-1]$，它的和可以用前缀和在 $O(1)$ 时间内得到．我们只枚举 $1\le s\le n$，不会把复制出来的起点重复计数．

枚举取盘数

对每个起点，依次检查 $k=L,L+1,\ldots,R$．只要有一个长度不满足要求，这个起点就不合格，可以立即停止检查．全部满足才把答案加一．

时间复杂度为 $O(n(R-L+1))$，空间复杂度为 $O(n)$．提前停止在有些输入上很快，但最坏情况仍然要检查很长一段，不能据此认为这个做法可以通过完整范围．

这个做法可以通过子任务 1 和 2，共 45 分．子任务 2 中 $L=R$，每个起点只需判断一次，复杂度自动降为 $O(n)$．

把许多个长度合成一次区间查询

现在的问题是，同一个起点要检查很多个 $k$．刚才的不等式也可以写成

这 $k$ 盘中的每一盘都贡献了一个 $na_i$，同时我们减去了 $k$ 份 $S$．因此，可以给每一盘重新记一个数

取走一段盘子时，直接把这段里的 $b_i$ 加起来，它就是 $nx-kS$．于是要求变成：从起点开始，长度在 $[L,R]$ 内的每一段，和都非负．

设复制后的 $b$ 的前缀和为 $P$，其中 $P_0=0$．固定起点 $s$，取 $k$ 盘的和为

右边的 $P_{s-1}$ 不随 $k$ 变化．所以我们不必逐一检查，只要找到所有可能的右端点中，前缀和最小的那个：

如果最小的那个都不小于 $P_{s-1}$，其他右端点当然也满足；如果最小的那个更小，它对应的长度就是一次不合格的取盘方式．这说明上面的区间判断与原要求完全等价．

用 ST 表预处理区间最小值，之后每个起点查询一次即可．预处理 $O(n\log n)$，查询总计 $O(n)$，空间复杂度 $O(n\log n)$．也可以建一棵只维护最小值的线段树，建树 $O(n)$，总查询 $O(n\log n)$，空间复杂度 $O(n)$．两种做法都可以通过全部子任务，得到 100 分．

子任务 3 为什么还能更简单

子任务 3 中，我们需要检查全部长度 $1$ 到 $n-1$．又因为

绕完整整一圈，前缀和会回到原来的值，即 $P_{j+n}=P_j$．

从 $s$ 出发时，所有可能右端点的前缀和，加上起点之前的 $P_{s-1}$，恰好对应一整圈的 $n$ 个前缀和位置．因此，所有取法都非负，当且仅当 $P_{s-1}$ 是这一圈的全局最小值．

只计算 $P_0,P_1,\ldots,P_{n-1}$，统计最小值出现的次数即可．不能再把 $P_n$ 算进去，因为它和 $P_0$ 对应同一个起点．

这条性质做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，可以获得子任务 3 的 20 分．和前面的枚举做法分别处理对应情况，可以得到 65 分．它也解释了为什么要比较前缀和，但不能直接套到一般的 $[L,R]$：一般情况下只要求一部分右端点满足条件，合法起点未必对应全局最小值．

还可以用单调队列

区间查询已经能满分．如果想继续优化，注意起点 $s$ 每增加 $1$，需要查询的区间

也恰好向右移动一格．这是固定宽度的滑动窗口最小值．

队列中保存前缀和的下标，使下标递增，对应的前缀和也递增．加入新位置 $j$ 时，如果队尾的前缀和不小于 $P_j$，就可以删掉队尾：新位置的值更小或相等，离开窗口的时间又更晚，被删的位置以后都不可能比它更合适．再把已经离开左边界的队首删掉，剩下的队首就是当前区间最小值的位置．

每个下标只会入队一次、出队至多一次，因此所有窗口的维护总共是 $O(n)$．加上读入和求前缀和，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，可以获得 100 分．

下面的实现采用这个做法．第一次只加入下标 $L$ 到 $R$，之后随起点移动加入右端点、删除过期下标．判断中使用 >=，平均值相等也必须计入答案．中间量绝对值不超过 $8\times10^{16}$，64 位有符号整数足够．

参考代码

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, L, R;
    cin >> n >> L >> R;
    vector<ll> a(n), p(2 * n + 1);
    ll sum = 0;
    for (ll &x : a) {
        cin >> x;
        sum += x;
    }
    for (int i = 1; i <= 2 * n; ++i)
        p[i] = p[i - 1] + n * a[(i - 1) % n] - sum;

    deque<int> q;
    int right = L - 1, ans = 0;
    for (int s = 1; s <= n; ++s) {
        while (right < s + R - 1) {
            ++right;
            while (!q.empty() && p[q.back()] >= p[right]) q.pop_back();
            q.push_back(right);
        }
        while (!q.empty() && q.front() < s + L - 1) q.pop_front();
        if (p[q.front()] >= p[s - 1]) ++ans;
    }
    cout << ans << '\n';
    return 0;
}