ACGO 正在蒸蒸日上！
赛时至少出现 333 个影响解题的大问题，比赛出成这样也是没谁了。
T1
看不出来哪里有橙。这玩意不 ABC A 题难度吗。
直接贴代码。
时间复杂度：O(n)O(n)O(n)。
T2
这场挑战赛质量最高的一题，真的。
我们开个桶，然后枚举 maple 序列两个元素的和是多少，求出对应的长度，取最大值。
时间复杂度：O(V2)O(V^2)O(V2)。
T3
由于只能往相邻的移动，所以最优方案就是选定一个点，然后让其他石子全都往这个点移动。而且要从两边开始移，这样可以使得多组石头一次移动，移动次数尽量小。
用两个前缀和和两个后缀和数组。
第一个前缀和数组和后缀和数组记录第 iii 个以前/以后的石子个数，第二个前缀和数组和后缀和数组记录前面/后面的石头搬到第 iii 个点所需最小次数。
然后枚举每一个点查询即可。
时间复杂度：O(n)O(n)O(n)。
T4
还是前缀和题。
注意到一个点可以向下 (Bi−Ai+m)mod m(B_i-A_i+m)\mod m(Bi −Ai +m)modm 次调到 AiA_iAi ，也可以向上 (Ai−Bi+m)mod m(A_i-B_i+m)\mod m(Ai −Bi +m)modm 次调到 AiA_iAi 。
而问题九转化成了分成两组，一组向下调，一组向上调，求次数最大值之和的最小值。
我们可以按向下调的次数排序，显然这样向上调的次数就是降序的。
所以我们只需要枚举向下调多少次之内就向下调是最优的，用前缀和优化。
时间复杂度：O(∑nlogn)O(\sum n\log n)O(∑nlogn)。
T5
已完成今日输出 Yes No 大学习。
很板的 01BFS。
题意可以转化成在这个方向上的权值为 000，不在的权值为 111。
BFS 的过程只需要权值为 000 的边加队首，权值为 111 的边加队尾就行了。
不会的也可以 dij。
时间复杂度：O(∑nm)O(\sum nm)O(∑nm)。
T6
我认为这题的问题有：
1. 这题出了有什么意义。
2. 这玩意为什么能作为挑战赛最难题。
3. 神人题面自己都弄不明白，数据也能乱造的吗。
4. 这题哪来的绿难度。
5. 施氏食狮史。
为简化问题，BiB_iBi 集合变成一个具体的数值 ∑c∈Bi2c−′a′\sum_{c\in B_i} 2^{c-'a'}∑c∈Bi 2c−′a′。
注意到不需要判断所有区间是否满足条件，只需要判断修改后的 [i−1,i][i-1,i][i−1,i] 和 [i,i+1][i,i+1][i,i+1] 就行了。
先考虑 [i−1,i][i-1,i][i−1,i]。
显然修改后的 Bi′B'_iBi′ 必须满足 Bi′∣Bi−1=Bi∣Bi−1B'_i|B_{i-1}=B_i|B_{i-1}Bi′ ∣Bi−1 =Bi ∣Bi−1 。
所以 Bi′B'_iBi′ 在 Bi∣Bi−1⊕Bi−1B_i|B_{i-1}\oplus B_{i-1}Bi ∣Bi−1 ⊕Bi−1 这些位必须为 111，而 Bi∣Bi−1B_i|B_{i-1}Bi ∣Bi−1 没有的地方必须为 000。
那么 Bi′B'_iBi′ 的 (Bi∣Bi−1)⊕(Bi∣Bi−1⊕Bi−1)=Bi−1(B_i|B_{i-1})\oplus (B_i|B_{i-1}\oplus B_{i-1})=B_{i-1}(Bi ∣Bi−1 )⊕(Bi ∣Bi−1 ⊕Bi−1 )=Bi−1 这些位可以为 000 也可以为 111。
同理，可以得出对于 [i,i+1][i,i+1][i,i+1]，Bi′B'_iBi′ 的位可以为 000 也可以为 111 也只有 Bi+1B_{i+1}Bi+1 ，其余都是固定的。
所以修改 BiB_iBi 结果不变就只有 2popcount(Bi−1&Bi+1)2^{\text{popcount}(B_{i-1}\&B_{i+1})}2popcount(Bi−1 &Bi+1 ) 种情况。注意要减去等于 BiB_iBi 的一种情况。
加起来即可。
时间复杂度：O(∑nm)O(\sum nm)O(∑nm)。
