维护序列,支持:
-
区间异或
-
查询区间子集异或值种数(包含空集)
\(n\le 2\times 10^5\),\(1\le q\le 4\times 10^4\),值域 \([1,10^9]\),TL=7s.
经典题。
操作 2 相当于查询区间线性基大小。
由于不能维护区间异或,作差分 \(b_i=a_i\oplus a_{i-1}\)。
可以得到 \(a_i=\oplus b_1\oplus \dots\oplus b_i\).
不难发现 \(a_l,\dots,a_r\) 的线性基相当于 \(a_l,b_{l+1},\dots b_r\) 的线性基。
操作 \(1\) 相当于单点异或,用线段树维护,查询时加入 \(a_l\) 查询线性基大小即可。
时间复杂度 \(O(q\log n\log^2 V)\).
标签:dots,10,le,Duff,Queen,异或,CF587E,线性,oplus From: https://www.cnblogs.com/SError0819/p/17813905.html