这 3000?
以下,\(\operatorname{op}(i)\) 代表对 \(i\) 进行一次操作。
我们考虑暴力。因为每一位都是分开处理的,我们考虑仅仅把一段区间的端点交换。即我们希望通过 \(\operatorname{solve(l, r)}\) 把 \(a_ia_j\) 交换而其他下标不动。一个显然的想法是,我们一定需要大量的前后缀异或操作和差分操作,以达到把两个数异或的目的。
那么我们不难思考出如下算法:
- 做操作 \(\operatorname{op}(j-2\sim i)\),然后 \(a_{i+k}=\oplus_{w=i+k\sim j-1}a_w\)。
- 还原 \(a_{i+1}\sim a_{j-2}\)。
- 做操作 \(\operatorname{op}(j-1\sim i+1)\),然后 \(a_i\oplus a_{i+1}\)。
- 还原 \(a_{i+1}\sim a_{j-1}\)。
然后发现最后没有必要还原,然后略作计算发现这东西能过。所以暴力能过这道题!
标签:题解,CF1748F,异或,操作,operatorname,sim,op From: https://www.cnblogs.com/Piggy424008/p/17938085/solution-cf1748f