Codeforces Round 882 (Div. 2) 题解
A. The Man who became a God
求出相邻两个元素的差值，去掉前 \(m\) 个大的差值以后的差值和即为答案
B. Hamon Odyssey
由按位与的性质可以知道，前缀与和 的值只会越来越小，只要和为 \(0\) 的时候我们就清空按位与前缀和，增加一下次数，如果最终次数不为 \(0\)，特判一下，次数加一即可
C. Vampiric Powers, anyone?
由于异或有以下性质：
所以每一次我们在最后添加数字时，都相当于消掉序列尾部的一段区间
又因为我们在选择区间时可以不选头部一段区间，所以题目相当于求 \(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}\)来说必定不同，所以我们直接扫一遍就可以了
时间复杂度 \(O(2^{2k}k^3)\)
F. The Boss's Identity
（待补）