A. The Man who became a God

求出相邻两个元素的差值，去掉前 \(m\) 个大的差值以后的差值和即为答案

B. Hamon Odyssey

由按位与的性质可以知道，前缀与和 的值只会越来越小，只要和为 \(0\) 的时候我们就清空按位与前缀和，增加一下次数，如果最终次数不为 \(0\)，特判一下，次数加一即可

C. Vampiric Powers, anyone?

由于异或有以下性质：

\[a\oplus b\oplus b=a \]

所以每一次我们在最后添加数字时，都相当于消掉序列尾部的一段区间

又因为我们在选择区间时可以不选头部一段区间，所以题目相当于求 \(a\) 序列的区间异或最大值

这个东西可以使用 0/1-Trie 维护

D. Professor Higashikata

首先从原字符串中要提出 \(m\) 个子串合并，通过交换操作使字典序最大，那么我们可以处理出原字符串中每个字符的优先级。我们将处理出来的优先级拼接起来作为字符串 \(p\)

直接扫一遍是平方级别的，用线段树标记打过的 \(tag\) 并跳过可以优化到 \(O(n\log n)\)

接下来就是计算操作次数。容易发现把 \(s\) 中的所有 \(1\) 放在 \(p\) 的开头位置即可，换句话说就是拿 \(1\) 的个数 \(cnt\) 去补在 \(p\) 的开头。所以我们只要维护 \(cnt\) 的值和 \(p\) 中 \([1,cnt]\) 中 \(0\) 的个数即可，因为在 \([1,cnt]\) 中的 \(0\) 总能找到后面的 \(1\) 补上

注意 \(cnt\) 可能大于 \(p\) 的长度，所以线段树的上界要 \(\min(cnt,tot)\)，\(tot\) 代指 \(p\) 的长度

那么后面显然是一个单点修改和区间加，用线段树维护即可

E. Triangle Platinum?

交互题

由于 \(n\le 5000\)，所以 \(5500−5000=500\)，考虑一下该如何利用这 \(500\) 次操作

我们如果对于一个长度为 \(k\) 的序列暴力，那么我们需要消耗 \((_3^k)\) 次操作，时间复杂度为 \(O(2^{2k}k^3)\)

我们选定 \(k=9\)，那么根据抽屉原理，这 \(9\) 个数中，必然有一个数出现至少 \(3\) 次

直接暴力找出这个数，记为 \(s\)，这三个数下标为 \(x,y,z\)，然后开始分类讨论。

\(s=1\)，那么我们顺序扫过去，当前为 \(now\)，如果询问 ? x y now 结果不是 \(0\)，那么我们可以确定 \(a_{now}=1\)，否则确定 \(a_{now}\not=1\)

接下来我们拿出 \(a_{now}\not=1\) 的 \(k\) 个数来暴力，这样就可以归类到第二种情况
\(s\not=1\)，考虑这个时候询问 ? x y now 的结果对于不同的 \(a_{now}\)来说必定不同，所以我们直接扫一遍就可以了