【连载】OI思考题1：大鱼吃小鱼

各位同学大家好！

本期开始， OI思考题 栏目将在账号上开始连载，欢迎大家讨论！

OI思考题是一种类似大学算法课程课后题的题目，希望同学们在讨论的过程中增进对问题研究方法的理解。

每一期会同时发布上一期的部分参考解答和资料。

第1期 大鱼吃小鱼

有一排 n 条鱼，每条鱼有一个体型值（正整数）a_i，一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己。吃完后自己的体型会加上被吃的鱼的体型。鱼之间位置的先后顺序不变。

问题1：每条鱼最多可以吃到多大的体型？

问题2（P9530）：单点修改 a_i，区间查询 [l,r] 内有多少条鱼可以吃完区间内其它所有鱼。（只有这个问题有修改和查询）

问题3：如果我们有一种道具，鱼每用一次道具可以吃掉任意一条相邻的鱼，无视体型，请你对于每条鱼求出，它吃完所有其它鱼最少需要多少个道具。

问题4：如果我们把吃鱼的规则改为只能吃右边（编号更大）和自己相邻的鱼（道具不受影响），问题2和3的结果会有什么变化？（你不能先操控别的鱼吃鱼，再用道具吃它）

问题5：如果我们允许小鱼吃大鱼，也就是定义常数 k(k\ge 0)，将题目条件改为“一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己的体型加 k”，问题3的结果会有什么变化？

问题6（JS2024/U477940）：如果我们去掉问题5中 (k\ge 0) 的限制，问题5的结果会有什么变化？

问题7：如果我们把问题5和6中的条件从差值改成比例，也就是定义常数 c(c\gt 0)，将题目条件改为“一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己的体型乘 c”，问题5（c\ge 1）和6的结果会有什么变化？

*问题8：尝试找到一个有意思的问题并改编一个 OI 题目。例如：如果我们把鱼放到树上，定义每条鱼占据一个树上连通块，两条鱼相邻当且仅当占据的连通块相邻，初始每条鱼占据一个点，被吃的鱼的连通块会被吃它的鱼占据，会发生什么？

本期节目由 勰码公益省选训练营 赞助播出。