2026.3.1
Hailiang 白石溪（creek）
\(\color{blue}{贪心}\)
先假设所有球都是蓝色的，那么有代价 \(\sum\limits_{i=1}^{n}b_i\)。计算如果此时把 \(i\) 个 球变成红色会增加的贡献 \(w_i = a_i-b_i+(i-1)c+(n-i)d\)。考虑如果把 \(k\) 个位置变成红色，如果直接加上 \(\sum\limits_{i是红色}w_i\) 会多算贡献。发现对于每两个红色位置，都会多算 \(c+d\) 的贡献。假设有 \(k\) 个红色位置，那么答案为 \(\sum\limits_{i=1}^{n}w_i+\sum\limits_{i是红色}w_i-\frac{k(k-1)}{2}(c+d)\)。题目要求最大化答案，那么就优先选择 \(w_i\) 大的加入。按照 \(w_i\) 降序排序，每次检查如果对答案有贡献就变成红色即可。
Hailiang 敏感词（that）
\(\color{blue}{后缀数组，线段树}\)
设屏蔽词的起点为 \(p_1,p_2,\cdots,p_m\)，\(d_i=p_i-p_{i-1}\)。那么答案为 \(p_m-p_1+len-\sum\limits_{d_i>len}(d_i-len)\)。把式子展开，\(\text{ans} = (p_{mx} - p_{mn} + len) - \left( \sum_{d_i > len} d_i - len \times \text{C}(d_i > len) \right)\)，其中 \(p_{mx}, p_{mn}\) 是当前集合中最大和最小的起始位置，\(\text{C}(d_i > len)\) 是所有大于 \(len\) 的间距的数量。考虑使用后缀数组。对于 \(hei\) 数组中大于等于某值 \(h\) 的一段区间，这些后缀对应的前 \(h\) 个字符是完全相同的。这意味着它们构成了同一个子串 \(T\) 的出现位置集合。考虑一开始把每个后缀看成一个集合，每次按照 \(hei\) 从大到小的顺序使用并查集合并 \(sa_{i-1}\) 和 \(sa_i\)，并更新答案。考虑如果计算 \(p_{mx},p_{mn},d_i\)。可以使用 set 维护并查集中每个点对应的屏蔽词起点。每次启发式合并即可计算 \(p_{mx},p_{mn}\)。当每次有一个新的 \(p\) 插入到集合中时，他都会破坏原有的一个间距，产生两个新的间距。使用权值线段树即可维护每次插入数字，删除数字，算出 \(d\)。
Luogu P3563 [POI 2013] POL-Polarization
\(\color{blue}{树的重心，背包}\)
把所有边全部指向其父亲，可以得到最小值是 \(n-1\)。对于最大值，考虑重心 \(rt\) 的若干子树。设他们的大小为 \(a_1,a_2,\cdots,a_m\)，那么就要求指向重心的子树大小和与不指向重心的子树大小和尽量相等，这就是一个背包问题。但是如果遇到菊花就炸了。考虑可以把大小相等的两个子树合并，相当于一个多重背包。使用二进制分组优化即可。