题解：P11620 [Ynoi Easy Round 2025] TEST_34

· · 题解

zky 在 WC 2025 讲课时针对类似题目给出了一个相当好写的 2log 做法。

本题可以被简化成单点修改，求区间线性基问题。求一个区间的线性基，可以考虑随机出该区间的 T=\log qV+\epsilon 个子集，然后将这些子集的异或和构成的线性基当成原区间的线性基。

正确性证明，可以参见 zky 的课件！

具体实现，维护 T 个支持单点修改，区间 xor 的数据结构，每个数据结构均有 \frac{1}{2} 的概率包含数组的一个元素。

这样你单点修改的时候，只修改那些包含被修改的元素的数据结构就行了。

这个做法常数相当小！而且就算没能观察出差分也可以硬上线段树维护区间 xor 区间 xor 和！

让我们一起赞美伟大的 zky 吧！\zky/\zky/\zky/