CF1630D *2400
记 \(B\) 表示所有能翻转区间长度的集合。那么对于任意 \(x,y \in B\)，都满足 \(x-y \in B\)。所以 \(\gcd(b_1,b_2,\dots,b_n) \in B\)。考虑长成什么样的序列满足要求。考虑记 \(g_i\) 表示第 \(i\) 个数是否翻转。记 \(f_i\) 表示 \(\bigoplus_{i=x \bmod g} g_x\)。 只有当所有 \(f\) 都相等时才满足要求。
然后 \(dp_{i,j}\) 表示前 \(i\) 个数，\(f\) 的异或值为 \(j\) 的 \(\sum a_i\) 的最大值。
CF1619H *2400
首先这东西一定是个置换环。如果没有交换操作很 naive，考虑怎么维护这个交换操作。
记 \(nxt_i\) 表示 \(i\) 跳 \(B\) 次后的结果。然后只会影响 \(B\) 个 \(nxt\)，暴力维护即可。
单次查询是 \(O(\frac{B}{n})\) 的。
取 \(B=\sqrt n\) 可以做到 \(O(n \sqrt n)\)。