意识流题解。
那些你不要的
场上写了一个二分答案 + 栈模拟，实在是太蠢了！
观察到每次一定会删一个奇数位的和一个偶数位的，最后只有一个奇数位的会保留下来，然后就完了。
比特迷宫
场上写了一个乱搞：每 \(24\) 个分一块，对于每块跑出一个最优解。然后把相差 \(2^k\) 的相同操作不断合并。
这样在随机数据下比较优秀，但不能过 hack. 加了 1000 次随机打乱，结果有一个 Hack 超了 300 次。
实际上应该可以构造到小于 \(160000\) 量级的？但是我不会.
官方题解的确定性做法：
将所有状态 \(S\) 按 popcount 从高到低处理。
核心观察：如果 flip 了 \(S\) 位置，那么设 \(T\) 为 \(S\) 去掉某一个 1 位（\(S\ \text{and}\ T = T\)），那么翻转一下 \(S\) 可以同时翻转任意若干个的 \(T\)。
实现上只需要把 \(S\) 的若干个 \(1\) 去掉得到 \(A\)，执行 \((A,S-A)\) 即可。
若 \(S\ \text{and}\ T = T\) 称 \(S\) 能覆盖 \(T\).
那么问题可以转化为，对于 popcount \(=k\) 的所有 \(S\)，选取一个覆盖集，使得能覆盖所有 popcount \(=k-1\) 的所有 \(T\)。
接下来贪心搞一搞，就可以得到总数为 \(157884\) 的覆盖集。
璀璨宝石
80 分做法：
考虑把答案表示成 \(\max(A,B,C,D,E,\lceil sum/2 \rceil)\)，这也是第一直觉的想法。
枚举某一个颜色作为最大值，可以求出 \(A/B/C/D/E\) 作为最大值的方案。
但是怎么求 \(\lceil sum/2 \rceil\) 能否取到最大值呢，可以转成计数，数出 \(sum\) 的总方案数减去 \(A/B/C/D/E\) 作为最大值的方案数，如果方案数 \(>0\) 就可行。
这样可以做到 \(O(n^2M^2)\).
考虑看作一个匹配问题，每次匹配两个球，而不是考虑 \(\max(mx,\lfloor sum/2 \rfloor)\)。（我觉得这一步实在太难想到了！）
考虑将问题划分成两个阶段。
第一阶段是把每次加进来的任意选两个消除；
第二阶段是钦定一种颜色 \(c\) 是之后最大的，每次都把新加进来的颜色和 \(c\) 消除，其他颜色不互相消除。
这样就有了自由操作的空间：我们可以在任意时间从第一阶段转换到第二阶段，对于所有这样的方案取 \(\min\)。（如果转换时间选错是不优的，但是在 dp 的时候可以任意时间转换，所以可以取到最优。感觉很妙！）
对于第一阶段，只需要记录当前剩下的颜色 \(c\) 和 \(c\) 多余的个数。
对于第二阶段，只需要记录当前钦定的颜色 \(c\) 和 \(c\) 多余的个数，如果是其他颜色多余则看作是负数个 \(c\)。
这样状态数就是 \(O(nM)\) 的了，并且第一种的多余 \(x\) 个可以和第二种的多余 \(x\) 个记在同一个状态里，所以状态数只有 \(f([0..4],[-M..M])\)。
暴力转移可以做到 \(O(n^2M^2)\)，利用单调队列优化第一种转移，可以做到 \(O(n^2M)\)。
火星式选拔
反重：求熵
太难了，我觉得这种题是不是初见杀，没见过这种题就做不出来。做的时候知道这是暴力解除限制的题，却一点也没有高分的想法。
赛时想法：
考虑一个一个消去变量。猜一个结论，对于第一个变量 \(a_1\)，值域可以分成若干段，\(a_1\) 取某一段值的时候，后面的答案是一个关于 \(a_1\) 的多项式，可以插值出来。然后不断二分下一段插值的端点。
但是这样做太劣了，只能跑 \(n\le 3\)。
正解也考虑了”一个一个变量消去，解除限制“，但是更加显式地把限制表示出来。
先钦定 \(n+1\) 号变量为 \(0\)，加入限制 \(a_i\ge a_{n+1},a_i\le a_{n+1}+T\).
从 \(1\) 到 \(n\) 一个个消去变量。
考虑如果 \(2\) 到 \(n\) 都确定了，那 \(1\) 一定会受到左、右的限制，也就是会有一个 \([l_1,r_1]\)。
此时，后面的每个变量都对 \(1\) 变量产生一个 \([l_j,r_j]\) 的限制，那最后 \(l_1=\max(l_j),r_1=\min(r_j)\)。
将贡献差分，变成 \(r_1 - (l_1 - 1)\)。考虑枚举某个端点（左/右），被后面的哪个变量限制得最强。也就是 \(\max,\min\) 是在哪个值取到的。这样共有 \(n!2^n\) 种枚举。
由于钦定了某个 \(j\) 对 \(i\) 限制最强，在 \([2,n]\) 之间会形成一些新的限制，在 dfs 枚举的时候顺便加入。
容易发现限制会形成一个树的结构，连边 \(i\to fa_i\)，\(n+1\) 是树的根。
这时转化成了这样的问题：要求 \(0\le a_i\le a_{fa_i}+w_i\)，求所有方案数.
每个点维护一个多项式 \(f_i(x)\) 表示根节点权值取 \(x\) 时子树内方案数为 \(f_i(x)\)。
在树上从下向上转移，令 \(F_i(x) = \sum_{j=0}^{x+w_i} f_i(j)\)，转移就是 每次把 \(F_i(x)\) 乘到 \(f_{fa_i}(x)\) 上。
由于 \(F_i\) 的项数恰好比 \(f_i\) 多 \(1\)，转移复杂度就是树形背包，为 \(n^2\).
于是总复杂度 \(O(n!2^n n^2)\)。
终于补完了所有 zky 场切的题
鸽子收费站
需要支持这样的操作：将 \([l_1, r_1]\) 中值在 \([l_2, r_2]\) 的元素全部置为 \(r_2\)。以及单点修改，单点查询。
这题居然能做到 polylog 的，很厉害。
考虑 Segment Tree Beats 式维护，在线段树上做，如果区间中有 \(\ge 2\) 个要被修改的值就递归，否则修改这个值。
在根节点上维护一棵平衡树，表示所有值去重后的结果。
对于线段树每个子节点维护一棵平衡树，每个节点连向线段树父亲节点中平衡树的对应节点。
考虑修改时，有 \(\ge 2\) 中要修改就要递归。而只有 \(1\) 种要修改时，不会改变儿子的平衡树，只可能要改变自己和祖先的。
标签：UNR,变量,一个,sum,补题,可以,考虑,节点 From： https://www.cnblogs.com/Rainbowsjy/p/17609460.html