//从出题那一刻起我就觉得这题可能肯定有别的解法(但是我太蒟蒻了我想不出来)

如果哪位大神能发现本题有除了题解之外的解法，欢迎分享 ovo 当然不排除没有其他解法的可能性 //逃

已知(可能)不可行的思路：

1. 先离散化，然后开一棵主席树，版本 i 代表区间 [1,i] ，每个叶子节点表示一个不同的收益期望值，节点的值表示该期望值出现了多少次乘以期望值；那么非叶子节点就表示区间加权和。要查询任意区间 [l,r] 就用版本 r 根节点减去版本 l-1 根节点。至此为止思路与 静态区间第k小 模板类似

   为了支持带修改，可以用树状数组维护主席树，将版本 i 原含义叠加为树状数组求和下的 [1,i] 版本和。那么原本的查询就变成了查询树状数组下 r 的所有 lowbit 版本减去 l-1 所有 lowbit 版本。至此为止思路与 动态区间第k小 模板类似。但是树状数组只能实现单点修改，不支持操作 2 的全长修改，所以依然无法实现

   未写完的代码在 这里

2. 为了支持全长带修改，可以在主席树基础上，用一棵线段树套主席树。那么把叶子主席树合并为非叶子主席树就需要使用线段树合并。线段树可以支持根节点修改(全场修改)，下传懒标签，进而支持区间查询。但是怀疑这么做会 MLE 或 TLE

   线段树节点数为 p 则合并的复杂度是 O(p) (大概？)，那么建树套树复杂度未知 //本蒟蒻尚未学线段树套线段树 //晚点学了再更新看看这个解法可不可行

3. 换一种很暴力的思路：我们用线段树套 map ，每个节点一个 map 和区间和，用 map 合并的方法实现 pushup 操作，这个建树过程的总时空复杂度应当是 O(n\log n) 的

   进行查询就直接线段树区间查询区间和即可

   要进行修改，等于先删除后插入，直接改根节点并进行懒标签下传，懒标签就按顺序记录所有的有效命令(可以稍微减一波枝)，问题就出在这里，在大量的操作后(特别是收益期望值值域很小的时候，因为剪枝大多不生效了)，懒标签会变的巨长无比，那么每次懒标签下传可以被卡到 O(m) 的复杂度，同时因为每个节点都存了巨量懒标签，空间复杂度也会爆到 O(4nm) ，因此 TLE+MLE 的代码在 这里

   考虑过每次懒标签下传之前先对懒标签序列进行化简操作，化简思路类似于原题解并查集，但是只要每次操作涉及的值不一样(比如 1\to 2\to3\to4\to\cdots )，最后需要下传的数目还是不变的，所以没有能够带来优化

4. 类似地，考虑用树状数组套 map ，但是树状数组只支持单点修改，这又非常难办了

5. 能不能反过来，开一棵权值线段树(节点数是离散后的期望收益值数目)，每个节点套维护这个权值出现的下标的数据结构(比如 map, 线段树等)，但是这样查询和修改好像都不好操作

6. 有无整体二分的解法(但是似乎不满足整体二分的五个前提条件的其中几个)

这个题直接树套树的话空间会爆，分块套的话，和原生题解感觉就一样了