比赛链接

给定一个长度为 $n$ 的序列，接下来 $m$ 个询问，每次询问区间 $[L,R]$ 中的所有连续子串中和不超过 $V$ 的最大值。

离线询问，将询问的 $V$ 和 $O(n^2)$ 个子串和从小到大排序后依次处理，于是题目变为支持单点最值操作和矩形最值查询的模板题。

考虑树套树，时间复杂度 $O\left(n^2\log^2 n+m\log^2 n\right)$，但是二维线段树会变卡常，瓶颈是修改操作。

考虑用树状数组代替线段树，对于单点最值操作树状数组时间复杂度 $O(\log n)$，区间最值查询操作时间复杂度 $O(\log^2 n)$。

ps. 如果是单点修改操作，树状数组时间复杂度变为 $O(\log^2 n)$。

经检验，线段树套树状数组最快，时间复杂度 $O\left(n^2\log^2 n+m\log^3 n\right)$。

另外二维树状数组次之，时间复杂度 $O\left(n^2\log^2 n+m\log^4 n\right)$，修改常数更小了但查询变慢了。