Candies

算法1（10%）

依据题意，暴力模拟即可。复杂度 O(NK) 。

算法2（30%）

观察到 算法1 的瓶颈在于寻找最大值和最小值。使用 STL set 维护这一过程可以将其优化到 O(logN) 。总复杂度 O(KlogN) 。

算法3（100%）

观察到当 K 很大时，每堆的糖果数会趋近相同（最多与最少相差为 0 或 1）。先将 a_i 排序，分别二分出 K 次操作能将糖果数小于等于 L 的糖果堆和大于等于 R 的糖果堆变为相同。如果 L\geq R，则若 N 整数糖果数输出 0 ，否则输出 1 ；如果 L<R ，则答案就是 R-L 。

Game

算法1（30%/70%）

不妨设初始位置在 x_1 的人属于 Alice 。为了使这个人移动到某个 y_j 有人的位置，Alice 的移动指令只有 n 种选择。枚举每种选择，每次暴力模拟移动所有人的位置，可以令操作后与最终位置重合的人都属于 Alice ，则剩下的人都属于 Bob。这样 Bob 就只剩下一种选择。再次暴力模拟检查这种选择是否可行即可。复杂度 O(nX) ，X 表示坐标范围。

算法2（100%）

算法1 中每次暴力模拟的效率很低，考虑用 Bitset 维护每位置有没有人，1 表示有人，0 表示没人。这样可以将复杂度优化到 O(\frac{nX}{64}) 。

Tree

考虑树的欧拉序（即长度为 2N-1 的 DFS 序），用线段树维护每个点到根的距离，则修改边权的操作可以转化为区间加法。设树上有两点 u,v ，它们的欧拉序分别为 a,b ，那么这两点的最近公共祖先 p 的欧拉序 c 一定满足 a\leq c\leq b ，且 p 到根的距离一定是欧拉序在区间 [a,b] 内的点到根的距离中最小的（边权为正）。用线段树维护区间内的 max(Dist_a+Dist_b-2Dist_c), a\leq c\leq b 即可。