Jiangly 讲题

CF2075F Beautiful Sequence Returns

能成为开头的一定是前缀 min，能成为结尾的一定是后缀 max。后面没听懂。

哈夫曼编码，但是 o/1 分支的代价（长度）不同。

因为一个点不能是另一个点的祖先，所以我们可以对于一个已有深度为 \(x\) 的节点，把它拆成 \(x+1,x+2\) 的两个节点。换个角度，一个 \(x,x+1\) 可以合成一个 \(x-1\)。

(a,b) 表示有 a 个 x，b 个 x+1

当 x-- 时，(a,b)->(b,a-b)

或者 (a,b)->(a+1,b)

还要记一个维度，最后答案是 \((1,0,n)\)。

后面没有听懂。

首先显然可以对序列排序。其次显然操作可以转化为“从大的开始减，每个数最多减 \(m\) 或者减到某一个值，最多减 \(mk\) 次，要求剩下的次数最少，剩下的减的次数会让最低一级里靠前的多减 \(1\)”。这里“减到某一个值”可以二分得出。

剩下的就好做了，虽然我不会。

显然是摩尔投票。check 的步骤是 trival 的，对每种颜色跑一个二位数点即可。

但是摩尔投票不能差分（我自己想到了，赢！）。我们采用分治的做法。

每行内部用一个线段树，行之间暴力，就可以。（我没听懂）

任何不能做差分的东西都可以用这个方法做。

二进制的每一位的绝对众数就是绝对众数（如有）的这一位。直接差分就做完了。（What?!! 这么简单？！！)