标签：左子 前缀 非负 RatingEstimator 线段 平均值

[ABC292Ex] Rating Estimator

题意可以转换为：

1. 单点修改。
2. 查询
   1. 如果不存在某一个前缀平均值不低于 \(B\)，则输出整体平均值；
   2. 否则，输出第一个不低于 \(B\) 的前缀平均值。

看到题，感觉可以线段树，但是要找的是第一个不低于的前缀平均值，怎么搞呢？

首先我们可以维护前缀和，这样操作 1 就对从该点往后的所有点区间后缀增加了一个值。

对于操作 2，我们考虑将所有数首先减去 \(B\)，这样要找的就是第一个非负的。

我们考虑维护最大值，在线段树上二分，若左子树的最大值非负，就往左子树走，否则往右子树走（这样就算是情况 2，也能在最终的边界中返回正确的答案）。

code

标签：左子,前缀,非负,RatingEstimator,线段,平均值
From： https://www.cnblogs.com/wscqwq/p/17653657.html