- 组题人：znstz, Crysfly
填写数字
来源：
排列计数
来源：
黑白棋子
来源：
不妨假设 $w\ge b$。
记 $mx_i$ 为删去 $i$ 之后剩下的连通块的大小最大值，那么假如 $w>mx_i$，则 $i$ 任意时刻必须是白色。
考虑当有点必须是白色时，答案就是把这些必须是白色的点删去后，剩下的大小超过 $b$ 的连通块个数。
否则，答案是 $1$ 或 $2$，而且为 $1$ 当且仅当存在某个点 $u$，删去 $u$ 之后存在两个连通块大小超过 $w$ 且存在另一个连通块大小超过 $b$。
我们记 $m=\min\{mx_i\}$，显然这个式子在重心处取到最小，所以我们以重心为根（有两个的时候就以那条边为根）。
当 $w\le m$ 时，没有点必须是白色，割掉一个点后最大的连通块一定是父亲的那个，所以记 $se_i$ 为儿子子树中的次大值，那么当 $b\le \max\{se_i\}$，答案是 $1$，否则答案是 $2$。
当 $w>m$ 时，必须是白色点的那些点形成了一个包含根的连通块，那么我们知道删去白色的点之后剩下的连通块一定是某个子树，那么一个子树是剩下来的连通块的条件就是 $mx_{fa_i}< w\le mx_i$，然后会所有 $b\le \min(w,sz_i)$ 有 $1$ 的贡献。
复杂度 $O(n)$。
冒泡排序
来源：
考虑枚举一个值 $V$，将序列中 $\ge V$ 的值看作 $1$，$< V$ 的值看作 $0$，将序列变成 $01$ 的形式。
对于所有的 $V$，求出对 $01$ 序列做完后区间内 $1$ 的个数，把这些答案相加就是总和。
发现对于一段后缀，它的每个 $0$ 每轮会向前移一格。一段前缀，如果有 $1$ 的话，一定会有 $1$ 交换到交界处。
那么对于一个值 $V$，我们询问的后缀 $[p,r]$ 新增的 $1$ 的个数其实是 $[p,p+k-1]$ 中的 $0$ 数与 $[l,p-1]$ 中的 $1$ 数取 $\text{min}$。
把暴力写出来，发现 $\text{min}$ 两边的贡献都是简单的主席树查询，取 $\text{min}$ 的情况也是简单的主席树二分，直接维护就好了。
时间复杂度 $O(n \log n)$。
