2021牛客暑期多校训练营3 I Kuriyama Mirai and Exclusive Or 差分 + 二进制分治
传送门
文章目录
- 题意：
- 思路：
题意：
给你一个数组aaa，让你实现以下两个操作之后输出数组aaa。
n≤6e5,ai≤230−1n\le6e5,a_i\le2^{30}-1n≤6e5,ai≤230−1
思路：
下面介绍的思路清奇，反正我想不到。
对于两个操作，显然对于异或操作顺序是没有影响的，所以对于第一个操作可以直接打个差分即可。
对于第二个操作，我们本能的想把括号拆开，但是括号中是加法对于异或来说没有分配律，所以考虑(x+(i−l))(x+(i-l))(x+(i−l))将加法转换成或，假设xxx的111的最低位置在2k2^k2k处，如果i−l<2ki-l<2^ki−l<2k，那么此时(x+(i−l))=(x∣(i−l))(x+(i-l))=(x|(i-l))(x+(i−l))=(x∣(i−l))，此时ai⊕(x+(i−l))=ai⊕(x∣(i−l))=ai⊕x⊕(i−l)a_i\oplus (x+(i-l))=a_i\oplus (x|(i-l))=a_i\oplus x \oplus (i-l)ai⊕(x+(i−l))=ai⊕(x∣(i−l))=ai⊕x⊕(i−l)，也就是先让iii位置异或上xxx，让后让[i,i+2k−1][i,i+2^k-1][i,i+2k−1]的位置分别异或上0,1,...,2k−10,1,...,2^k-10,1,...,2k−1。所以我们记一个f[k][i]f[k][i]f[k][i]数组表示是否需要将[i,i+2k−1][i,i+2^k-1][i,i+2k−1]的位置分别异或上0,1,...,2k−10,1,...,2^k-10,1,...,2k−1，之后将x+(1<<k),l+(1<<k)x+(1<<k),l+(1<<k)x+(1<<k),l+(1<<k)即可。
这样一直推下去，到最后会剩下一段小区间，这段区间我们直接倒着来一遍即可，因为他的后k−1k-1k−1位都是000，所以也满足上面的性质。
我们记了一个fff数组，个人感觉怎么用它也是一个比较难想到的点。我们可以用类似倍增实则是倍增的逆过程来递推下去，是一种分治的思想。
考虑当前遍历到了f[i][k]f[i][k]f[i][k]，那么我们可以将其分成两段来看，两段分别是[i,i+2k−1−1],[i+2k−1,i+2k−1][i,i+2^{k-1}-1],[i+2^{k-1},i+2^{k}-1][i,i+2k−1−1],[i+2k−1,i+2k−1]。
对于第一段，我们直接将f[i][k−1]f[i][k-1]f[i][k−1]标记一下，让后等分治下去处理即可。对于
对于第二段，我们将f[i+2k−1][k−1]f[i+2^{k-1}][k-1]f[i+2k−1][k−1]标记一下，这样还不够，因为这一位及其之后应该异或上2k−1,2k−1+1,...,2k−12^{k-1},2^{k-1}+1,...,2^k-12k−1,2k−1+1,...,2k−1，根据上面的转换公式，我们可以将i+2k−1i+2^{k-1}i+2k−1差分数组的位置异或上2k−12^{k-1}2k−1即可，这样就可以不断的分治递推下去，代码写起来很像倍增的逆过程。。
总结
以上是生活随笔为你收集整理的2021牛客暑期多校训练营3 I Kuriyama Mirai and Exclusive Or 差分 + 二进制分治的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 蚂蚱的功效与作用、禁忌和食用方法
- 下一篇： 2021牛客暑期多校训练营3 C Min