CodeForces 242E "XOR on Segment"（线段树）

传送门

•题意

　　给你一个包含 n 个数的序列 a，定义序列上的两个操作：

　　　　（1）$1,l,r\ :\ ans=\sum_{i=l}^{r}a_i$;

　　　　（2）$2,l,r,x\ :\ \forall\ i \in[l,r],a_i = a_i\ xor\ x$;

　　输出操作（1）对应的 ans 值；

•题解

　　因为是异或操作，而异或设计的运算都是在二进制上进行的；

　　所以考虑按照二进制位建立线段树；

　　对于每个叶节点，将对应的数转化成二进制的每一位存入到节点信息中；

　　然后就是区间更新，区间查询操作；

•Code

　　CodeForces242E(1).cpp

•CF242E升级版

　　题目来源与【2019ICPC亚洲区域赛银川赛站网络预选赛A. Simple Data Structures】

　　相比于 CF242E 这道题，对序列的操作增加了两个：

　　　　（1）$1,l,r\ :\ ans=\sum_{i=l}^{r}a_i$;

　　　　（2）$2,l,r,x\ :\ \forall\ i \in[l,r],a_i = a_i\ xor\ x$;

　　　　（3）$2,l,r,x\ :\ \forall\ i \in[l,r],a_i = a_i\ |\ x$

　　　　（4）$2,l,r,x\ :\ \forall\ i \in[l,r],a_i = a_i\ \&\ x$

•思路

　　和上题思路差不多，考虑到开 20 棵线段树维护以上操作；

　　难点在于如何 lazy，以及如何 pushDown()；

　　考虑到 ^,|,& 的特点；

　　对于某个数的二进制的第 i 位，假设为 bit[i]；

　　易得 bit[i] ^ 0 = bit[i] , bit[i] | 0 = bit[i] , bit[i] &1 = bit[i];

　　　　 bit[i] ^ 1 : 相当于反转 bit[i]；

　　　　 bit[i] | 1 = 1;

　　　　 bit[i] & 0 = 0;

　　也就是说只有后三个操作才有用；

　　考虑到 bit[i] 可能在这之前不止做依次操作；

　　但是有一点可以肯定，遇到 bit[i] | 1，bit[i] = 1，不管其之前做过何种操作；

　　同样，遇到 bit[i]&0，bit[i]=0;

　　而如果先遇到 &0 , 在遇到 ^ 1，相当于将 bit[i] 赋值为 1;

　　反之，如果先遇到 |1 , 在遇到 ^ 1，相当于将 bit[i] 赋值为 0;

　　这样的话，定义 lazy 有四个取值：

　　　　$lazy=\begin{cases} -1\ ,\ no\ operate\\ \ 0\ \ ,\ become\ 0 \\ \ 1\ \ ,\ become\ 1 \\ \ 2\ \ ,\ reverse\end{cases}$;

　　向下传递懒惰标记的时候，要结合父节点的 lazy 和子节点的 lazy 进行更新；

•Code

　　CodeForces242E(2).cpp

巴特西

CodeForces 242E "XOR on Segment"（线段树）

•题意

•题解

•Code

•CF242E升级版

•思路

•Code

最新文章

热门文章