A

直接模拟 进制不进位加法就行了。

B

容易发现异或操作每两位之间是独立的，所以来按位考虑。

对于每一位，容易发现只有 个不同的值，可以直接 暴力枚举计算答案。

时间复杂度 。

C

为了使转移更方便，我们先按照 从大到小排序，容易发现后面只可能往前跳。

一个简单的想法是直接转移前面数值最大的，但是显然不正确，因为有可能无法转移。

所以记录最大值和与最大值处于不同组的次大值即可。

时间复杂度 。

D

经过观察有一个结论：如果我想让一个点赢，我肯定把他放到最后面，因为如果我不这么干，当经过我之后我就要硬吃后面所有点的权值，那我让他在前面打架必然不劣。

所以问题就变成了前面的人最后打出来的最小值。

假设我们现在有两个计数器 和 ，我们认为目前站在台上的人的权值为 ，我们惊奇地发现，把一个人 ，就相当于是给 和 中的较小值加上 。

然后我们又惊奇地发现，给 和 分组后得到他们的绝对值最小值必然能够构造出一个合法的排列使得最后能够得到 和 。

原因显然，因为每次选择其中还没有被选择的最小值进行选择必然是最优的，如果存在一个时刻，里面的最小值已经选满，而最大值还要再选一个，则这种情况必然不优，把最大值还要选的那个丢给现今的最小值肯定能让答案变小。

则问题就变成了，现在有若干个点，你要给他们赋正负号，使得最后值最小，要支持插入。

这是一个经典的背包问题，使用 bitset 优化背包即可通过，时间复杂度 。

（本来有想一个优化合并前后缀背包的 trick，但是发现这么弄数据强度不高便作罢）

E

把这个问题拆成询问某个颜色是否在这些子区间内出现。

先考虑正常的做法，对于一个点，假设他在点 ，上一个颜色跟他相同的点在点 ，则我们认为左端点在区间 ，右端点在区间 的区间的颜色 是颜色 贡献的，然后就可以直接求解答案了。

我们直接把式子写出来那就是总共有 个区间被他贡献了。

则我们现在来考虑枚举一下 ，然后进行分类讨论。

如果 是定值，则考虑 的取值，要么是上一个定值，要么是中间的 给的贡献，如果是定值，意味着中间的 的取值都不是 ，如果是中间的随机值，则我只关心我取到了哪里，我取到的位置 ，贡献 ，他前面的我不在乎，贡献 ，他后面的我要求必须不是定值，贡献 。

容易发现这个东西随着下标的推移做的是全局修改，而前面的部分就算超过了定值， 也并不会造成影响，所以可以直接用前缀和做预处理。

如果 不是定值，那就很好办，考虑对于前面的每一个颜色 ，我都有 的概率取到，那我们把 的概率提出来，直接把定值的式子和起来就做完了。

时空复杂度 。

F

如果继续使用 E 中的刻画，难以解决 F，我们考虑换一个更厉害的转化。

我们还是考虑每个颜色对区间的贡献，然后进行扫描线，则右端点在点 的时候，假设第 个颜色上一个出现的位置为 ，则左端点的位置只要在区间 之间，颜色 就会产生 的贡献。

由期望的线性性，，则我们只需要考虑维护 就行了，考虑对于第 个点，他在一个区间里面随机，设 为区间长度，则有 的概率保持原样， 的概率变为 ，相当于操作区间乘与区间加，因为求的是子区间，还需要一个历史和，然后就可以通过。

时间复杂度

G

喜欢使用原题机的小朋友们你们好啊，这个题其实是 CF1920F2 的无敌加强，做法毫无关联。

考虑有什么办法能够刻画路径把岛屿包括起来的形态，考虑使用题面给出的刻画，那就是把这个路径抠出来丢掉之后岛屿和边界不联通。

建个超级源点连接所有岛屿，边界再连接超级汇点，现在问题就是咋删去一些点使得源汇点不联通。

容易发现假设现在起点为 ，有一个点 是路径包含的当且仅当有一条自 到 的路径上最小点权最大不小于某个定值。

这个形式很像重构树，所以建立重构树，然后就发现每个点必然是在上面删除一整个子树，用 dfn 序刻画一下，就变成了删掉一个区间的点，问能不能使得源汇不联通。

具体地这个可以考虑把整个段复制一遍丢到最后面，然后维护 表示区间以 开头，最多保留到 能够使得源汇不联通， 的求法有很多种，std 写的是线段树分治，实际上还整体二分也可以维护，甚至常数小很多，这个问题有一个强制在线版本 link。

可以使用 LCT 做到一个 log。