分 块 大 法 好
题面
给定一个长为$n$($n<=10^5$)的数组
数组里的数不超过$10^6$
有两种操作:
1:求sum$[l,r]$;
2:对$[l,r]$中的所有数和$x$异或
操作数$m<=5*10^4$
思路
挺好的一道题。
首先看到这题想到用一个数据结构来维护。
那是什么呢?线段树?分块?
都可以。
但考虑到一个问题——区间异或没有逆分配律。
那怎么办。显然一般的线段树与分块达不到我们的要求。
考虑把每一个数拆开,因为数组里的数不超过$10^6$,所以只需要拆$20$位就可以满足需要。
然后大力分块,每块维护当前这块数$1到20位$的$1$的个数与本块当前的标记$0或是1$。答案就是$[l,r]$中$[1,20]$位分别乘上$2的[1,20]$次方。
代码写得自认为很清楚了。
自己康康吧。
代码
1 |
|