原题连接
可以发现集合对称差就是异或运算。
每个点都记一个长度为值域的 bitset，每一位都表示根到他有没有奇数个这个数字。
那么 \(a_x\) 改为 \(v\) 的修改就变成了修改子树的所有点的 bitset，每次将子树中所有点的第 \(a_x\) 位取反，再将第 \(v\) 位取反。
查询就是 \(u\) 的 \(bitset\oplus v\) 的 \(bitset\)，因为 \(u\) 与 \(v\) 的 lca 被异或的两次，所以还要将最终的 bitset 的 \(a_{lca}\) 位给取反。
最后回答第 \(k\) 个 \(1\) 的位置即可，需要手写 bitset。
但这道题还没做完，因为空间太大了……
实际上我们随机选 \(\sqrt n\) 个点，作为重要点，只记录这些点的 bitset 即可。
每次操作也只修改它们的，询问的话，先暴力跳到离它们最近的重要点，由于每个点到最近重要点距离期望 \(\sqrt n\)，所以我们就有复杂度的保证了。
复杂度？修改一次：\(\sqrt n\)。询问一次：\(\sqrt n+\frac{n}{w}\log w\)
标签：修改,题解,复杂度,取反,sqrt,S16.23,12.2,bitset From： https://www.cnblogs.com/includec/p/17725698.html