2020-2021:teams:mian:gary:mos_algorithm_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/28 21:55] gary |
2020-2021:teams:mian:gary:mos_algorithm_tree [2020/05/28 22:27] (当前版本) gary |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 总结时用到的博客： | 总结时用到的博客： | ||
| - | https:%%//%%blog.csdn.net/qq_39759315/article/details/88553210 | + | [[https://blog.csdn.net/qq_39759315/article/details/88553210|https://blog.csdn.net/qq_39759315/article/details/88553210]] |
| - | https:%%//%%www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html | + | [[https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html|https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html]] |
| ==== 分块方式 ==== | ==== 分块方式 ==== | ||
| - | 首先需要解决bzoj1086王室联邦，此题的解法即为分块的方法 | + | 首先需要解决$bzoj1086$王室联邦，此题的解法即为分块的方法 |
| - | 下只简述过程，每块内的节点个数在$[B,3B]$之间，操作方式为维护一个栈，从根节点开始dfs，对于某一点x： | + | 下只简述过程，每块内的节点个数在$[B,3B]$之间，操作方式为维护一个栈，从根节点开始$dfs$，对于某一点$x$： |
| - | - 记录栈底的位置flg； | + | - 记录栈底的位置$flg$； |
| - | - 先访问所有子树，若访问完某棵子树后$top-flg\ge B$,则将stack[flg+1]至stack[top]中的点分为一块； | + | - 先访问所有子树，若访问完某棵子树后$top-flg\ge B$,则将$stack[flg+1]$至$stack[top]$中的点分为一块； |
| - | - 再将x压入栈。 | + | - 再将$x$压入栈。 |
| 最后栈中剩余的点加入最后一个块中 | 最后栈中剩余的点加入最后一个块中 | ||
| 行 21: | 行 21: | ||
| ==== 树上莫队的具体操作 ==== | ==== 树上莫队的具体操作 ==== | ||
| - | <HTML><ul></HTML> | + | * 带修改问题对时间的排序方式与普通莫队相同 |
| - | <HTML><li></HTML><HTML><p></HTML>带修改问题对时间的排序方式与普通莫队相同<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | === 在序列上操作 === |
| - | <HTML><li></HTML><HTML><p></HTML>在序列上操作<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | * 欧拉序<html><br></html>$dfs$遍历序列，当访问到结点$i$时加入序列，回溯至$i$时再将$i$加入序列 |
| - | <HTML><li></HTML><HTML><p></HTML>欧拉序<HTML></p></HTML><HTML></li></HTML> | + | * 定义$in[i]$表示在欧拉序$A$中第一次出现的位置，$out[i]$表示$i$第二次的位置<html><br></html>对于路径$x$到$y$上的询问，不妨设$in[x]<in[y]$ |
| - | <HTML><li></HTML><HTML><p></HTML>dfs遍历序列，当访问到结点i时加入序列，回溯至i时再将i加入序列<HTML></p></HTML><HTML></li></HTML> | + | * 若$lca(x,y)=x$,统计欧拉序中子序列$A[in[x]],...,A[in[y]]$中的出现过一次的节点的值即可回答询问<html><br></html>可以简单画图证明若是路径上的点当且仅当只其在子序列中只出现一次 |
| - | <HTML><li></HTML><HTML><p></HTML>定义in[i]表示在欧拉序A中第一次出现的位置，out[i]表示i第二次的位置<HTML></p></HTML> | + | * 若$lca(x,y)\neq x$,统计欧拉序中子序列$A[out[x]],...,A[in[y]]$中的出现过一次的节点的值以及$lca(x,y)$的值即可回答询问<html><br></html>通过画图会发现$lca(x,y)$并不在序列中，需要额外统计 |
| - | <HTML><p></HTML>对于路径x到y上的询问，不妨设in[x]<in[y]<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>若$lca(x,y)=x$,统计欧拉序中子序列A[in[x]],…,A[in[y]]中的出现过一次的节点的值即可回答询问<HTML></p></HTML> | + | === 在树上操作 === |
| - | <HTML><p></HTML>可以简单画图证明若是路径上的点当且仅当只其在子序列中只出现一次<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>若$lca(x,y)\neq x$,统计欧拉序中子序列A[out[x]],…,A[in[y]]中的出现过一次的节点的值以及$lca(x,y)$的值即可回答询问<HTML></p></HTML> | + | * 直接在树上操作的问题在于并不能类似序列中一样只在左右移动，因而考虑记录一个$vis$数组，表示结点是否在当前处理的路径上，<html><br></html>对于路径$(u_1,v_1)$到$(u_2,v_2)$的转移，只要将路径$(u_1,u_2)$和$(v_1,v_2)$上的点的$vis$值全部取反后在统计答案即可 |
| - | <HTML><p></HTML>通过画图会发现$lca(x,y)$并不在序列中，需要额外统计<HTML></p></HTML><HTML></li></HTML><HTML></ul></HTML> | + | * 需要注意在维护路径上点是并不考虑路径两端点的$lca$，需要将其单独统计,<html><br></html>上述方法的可行性以及不维护$lca$的原因如下(引用VFleaKing的证明) |
| - | <HTML></li></HTML> | + | <HTML><ul></HTML> |
| - | <HTML><li></HTML><HTML><p></HTML>在树上操作<HTML></p></HTML> | + | <HTML><li></HTML> <HTML><p></HTML>T(v, u) = S(root, v) xor S(root, u)<html><br></html>观察将curV移动到targetV前后T(curV, curU)变化： <html><br></html>T(curV, curU) = S(root, curV) xor S(root, curU) <html><br></html>T(targetV, curU) = S(root, targetV) xor S(root, curU) <html><br></html>取对称差： <html><br></html>T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU)) <html><br></html>由于对称差的交换律、结合律： <html><br></html>T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV) <html><br></html>两边同时xor T(curV, curU)： <html><br></html>T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV) <html><br></html>发现最后两项很爽……哇哈哈 <html><br></html>T(targetV, curU)= T(curV, curU) xor T(curV, targetV)<HTML></p></HTML> |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>直接在树上操作的问题在于并不能类似序列中一样只在左右移动，因而考虑记录一个vis数组，表示结点是否在当前处理的路径上，对于路径$(u_1,v_1)$到$(u_2,v_2)$的转移，只要将路径$(u_1,u_2)$和$(v_1,v_2)$上的点的vis值全部取反后在统计答案即可<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>需要注意在维护路径上点是并不考虑路径两端点的lca，需要将其单独统计，上述方法的可行性以及不维护lca的原因如下(引用VFleaKing的证明)<HTML></p></HTML> | + | |
| - | > <HTML><p></HTML>T(v, u) = S(root, v) xor S(root, u) 观察将curV移动到targetV前后T(curV, curU)变化： T(curV, curU) = S(root, curV) xor S(root, curU) T(targetV, curU) = S(root, targetV) xor S(root, curU) 取对称差： T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU)) 由于对称差的交换律、结合律： T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV) 两边同时xor T(curV, curU)： T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV) 发现最后两项很爽……哇哈哈 T(targetV, curU)= T(curV, curU) xor T(curV, targetV)<HTML></p></HTML> | + | |
| - | <HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>总结一下树上的操作和序列的不同点<HTML></p></HTML> | + | |
| - | <HTML><ol style="list-style-type: decimal;"></HTML> | + | |
| - | <HTML><li></HTML>分块方式不同<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>无法直接类比普通莫队序列上的操作，需要通过一些辅助使树上操作变成欧拉序上的操作，或者直接在树上移动，移动是都是通过vis数组判断节点的值是否需要统计(添加或删除)<HTML></li></HTML><HTML></ol></HTML> | + | |
| <HTML></li></HTML><HTML></ul></HTML> | <HTML></li></HTML><HTML></ul></HTML> | ||
| + | |||
| + | === 总结 === | ||
| + | |||
| + | 总结一下树上的操作和序列的不同点 | ||
| + | |||
| + | - 分块方式不同 | ||
| + | - 无法直接类比普通莫队序列上的操作，需要通过一些辅助使树上操作变成欧拉序上的操作，或者直接在树上移动，移动是都是通过vis数组判断节点的值是否需要统计(添加或删除) | ||
2020-2021/teams/mian/gary/mos_algorithm_tree.1590674105.txt.gz · 最后更改: 2020/05/28 21:55 由 gary
