526互联

【题解】Trees and XOR Queries Again - Codeforces 1902F

发布时间 2023-12-05 07:58:44作者: purinliang

https://codeforces.com/contest/1902/problem/F

方法一

可以从树上路径想到轻重链剖分（也可以用其他种类的LCA算法），然后从数的异或表示很容易想到线性基。

然后因为是无修改的，所以可以轻重链剖分+ST表+线性基。具体来说就是：

先进行轻重链剖分。然后把每次在链上的区间查询接到ST表上，然后ST表中存储[L,R]下标范围的线性基。

然后ST表可以延迟初始化，毕竟在树上很多区间的结果其实是无用的，延迟初始化的方法是用个 inited 标记，然后查询ST的数据之前先dfs一次，如果没有被初始化则递归调用dfs进行初始化并打上 inited 标记。这个方法对其他版本的ST表没有太大作用因为其他版本的ST表的初始化是O(1)的。

初始化复杂度：轻重链剖分初始化O(n)，ST表初始化O(n*logn)*合并复杂度，线性基合并复杂度O(B)。总体复杂度O(n + n*logn*B) = O(n*logn*B)
查询复杂度：q次查询，每次查询，轻重链剖分跳转 O(logn)，ST表回答O(1) *合并复杂度，线性基合并复杂度O(B)。总体复杂度O(q*logn*B)

方法二

很显然倍增LCA算法也是可以的。注意倍增LCA的时候存储每个节点u向上跳2i步走到的父亲节点，同时也是向上跳2i步过程中覆盖到的所有的点。所以说

LB[u][0] 包含 a[u] 和 a[p] 两个数字
LB[u][i] = LB[u][i - 1] 和 LB[pa[u][i - 1][i - 1] 的结果

这里也需要一个小trick卡常数，就是求解路径上的所有点的线性基的时候，要先求出LCA的位置L点，然后再分别从X点和Y点直接跳到L点，这样只需要合并2轮，反之如果先把X点跳到和Y点同样的深度，再X点和Y点一起向上跳到L点的过程中合并线性基，则要合并3轮，事实证明这里的常数确实是偏大的。

上面两个方法的启发是，如果某个操作不是O(1)的，那么要想一些小trick来减少这个操作的次数，为此可以多做几轮O(1)的其他操作。对于第一个方法，浪费的O(1)的操作是 inited 标记和每次访问之前的dfs。对于第二个方法，浪费的O(1)操作是X点和Y点重复进行了求LCA的过程，具体来说是用 3次的跳跃操作（求X点和Y点的LCA=L点）O(logn)+2次把X/Y点提升到L点高度的跳跃操作O(logn)+2次线性基合并操作O(log^2n) 代替了 3次的跳跃操作（求X点和Y点的LCA=L点）O(logn)+3次线性基合并操作O(log^2n)。

初始化复杂度：倍增LCA初始化O(n*logn)*合并复杂度，线性基合并复杂度O(B)。总体复杂度O(n*logn*B)
查询复杂度：q次查询，每次查询，倍增LCA跳转 O(logn)*合并复杂度，线性基合并复杂度O(B)。总体复杂度O(q*logn*B)

方法三

上面的做法是硬套数据结构的解法。官方解法和jiangly的方法一样。

对于每个节点u，记录其到从根节点r的路径上，遇到的使得线性基数量+1的节点的深度。注意这里的路径是有方向的，因为做LCA的时候要往上跳，所以要记录在往上跳的过程中碰到的哪些使得线性基增加的节点，把他们合并入此次查询的线性基中。

说得很好听，但是怎么做呢？

假设已经计算出了节点u的父亲节点p的结果（一个线性基，其中插入的每行记录了插入点的深度），考虑如何从p转移到u。

很明显，可以先把u节点的权值加入线性基，然后把父亲节点p中的结果从深度最大的插入，直到深度最小的。（选择排序）

需要注意的是经典版本的线性基写法中，是个上半阶梯矩阵（也就是说每一行的最高位对至少比上一行偏右1位（下降1位））但并不代表线性基中的数字一定在集合中出现，同时深度也不能保证。

jiangly的写法是将父亲节点p的结果复制，然后把u节点的权值加入，遇到了某一行已经被占领的话，则用u这一行代替此行（设带他来的节点为v），然后把v的这一行的结果继续往下插入，相当于就是把每一行往下挤一下。这个方法很巧妙，把O(B^2)的选择排序换成了O(B)的插入排序。

复杂度 O(n*B) 然后就得到了每个节点u，记录其到从根节点r的路径上，遇到的使得线性基数量+1的节点的深度。

下一步，对每次查询的x点和y点做LCA，求出LCA的深度dep[L]，复杂度O(logn)。然后把点x和点y的线性基中，>=深度dep[L]的行合并到一个新的线性基中，复杂度O(B)，这个线性基就不带有比L还高的点的信息了。

初始化复杂度： O(n*B)
查询复杂度：单次O(logn+B)，总共q次。

这是一个带有额外信息的线性基，然后提供了一种幺半群的维护思路，也就是从每个节点往上进行思考，从父节点转移，用新节点的数据插入父节点的数据中，淘汰掉父节点中旧的数据。