GDKOI2021普及组Day1B灌水
1815+
作者：crxis 发布：2021-02-02 分类：线段树
题目大意：一个凹凸不平的水槽，要使某个位置水量达到高度y，需要灌多少水？（已知每个位置的水量，多次询问！）
解题思路
暴力程序如下：自该位置开始，左边比他低的和右边比他高的都灌满水。
不难发现，程序满在查找，只要找到第一个大于等于k的位置，就可以用前缀和了。如果区间是[l, r]，那么总面积是k*(r-l+1)，已有面积是s[r]-s[l-1]。
怎么快速查找第一个大于等于k的位置呢？线段树肯定都可以解决。
以找左边第一个大于等于k为例：结点记录区间最大值，如果存在大于等于k则先找右边，因为右边的更加接近；找到几返回，否则返回左边的答案。
程序实现
当然，使用ST表也可以解决，我可以二分查找这个位置。
普及组同学还可以用分块来做：
多分几块速度更快：
