2021/11/17 T1 春节十二响

Solution

考试的时候想了1个半小时，感觉自己智商下降地越来越快了。/kk

我们发现我们直接树上启发式合并就做完了，因为子树之间互不影响，而你子树的根也不能和子树内的点放在一起。

复杂度是 \(\Theta(n\log^2 n)\) 的。

有一个 \(n\) 的个点的树，有 \(m\) 次操作，每次为以下两种之一（集合为可重集）：

\(n,m\le 10^5,\sum k\le 5\times 10^5\)

很愚蠢，但是我又没有看出来。/kk 真的要退役了

我们可以发现的是，两个路径的交点一定包含两者中的一个 lca，然后我们就做完了。注意 \(\sum k\) 只能带一只 \(\log n\)。

定义一个序列为好的，当且仅当一个颜色都在同一个段里面。

给你一个序列，每次操作你可以将某颜色在序列上的所有位置改成另一颜色，使得最终序列是好的。

我们定义代价为最终序列与原序列不同的位置数量（不是操作次数）。

有 \(T\) 次询问，每次将一个位置进行修改，问修改后的答案。

\(n\le 2\times 10^5\)

我们发现对于颜色 \(c\) 求出出现左端点 \(l_c\)，出现右端点 \(r_c\)，那么区间 \([l_c,r_c]\) 必定被染成相同颜色。

我们设 \(b_i\) 为 \(i,i+1\) 都被 \([l_c,r_c]\) 都被包含的 \(c\) 的个数。那么 \(b_i=0\) 的时候 \(i\) 一定是一个相同颜色区间的右端点。而一个区间的贡献就是大小减去出现次数最多的颜色的出现个数。前者综合为 \(n\)，我们直接求后者即可。

我们将 \([l_c,r_c]\) 中 \(c\) 的出现个数赋值到 \(l_c\) ，那么，一个区间的贡献就是区间值的最大值，也即是说，我们求出 \(b_i=0\) 的两者之间的最大值之和即可。

考虑怎么维护，实际上我们可以维护区间 \(b_i\) 最小值，值的最大值，最左边最小值及左的值的最大值，最右边最小值及右的值的最大值，以及会产生的贡献和。

复杂度 \(\Theta(n\log n)\) 的。