CF587E Duff as a Queen

发布时间 2023-11-06 22:14:45作者: SError

维护序列,支持:

  • 区间异或

  • 查询区间子集异或值种数(包含空集)

\(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)\).