Dragons

最优方案一定是选择一个团，并在团里平均分配点权。 实际上，定义一个点 \(u\) 的权重 \(w_u\) 为 \(\sum\limits_{(u,v)}s_v\)，那么如果方案中 \(w_x>w_y\)，将 \(y\) 去掉并将其点权加在 \(x\) 上一定更优，所以答案一定会被调整成一个团。 对于 ......

来道喜闻乐见的DS题，这题虽然比较套路但还是挺有趣的 一个朴素的想法就是用类似于珂朵莉树那样的方式维护所有内部等级相同的区间，但当操作数量上去后，显然分出的区间数量就变得不可控了，无法处理 另一个朴素的想法就是对于不同等级的龙维护它们的所有信息，直接暴力记录的话肯定不行，但考虑到操作的方式是从\(x ......