禁食后人
查看原帖
禁食后人
826236
Kremake楼主2024/4/25 10:18
  1. 在link-cut-tree使用换根操作时,1−>21->2 或者 2−>12->1 时 最低不为1和最低不为2的标记要直接交换(神奇的是直接对单点修改可以有 50p50p ),因为在splay时不能保证子树全部都被旋转过,信息无法直接维护,但是直接交换可以保证子树的顶点信息正确,保证了继承正确\

这是我对拍跑半天出来的hack数据

5
16 9 2 
10 6 3 
15 12 4 
11 7 5 
14 13 8 
0 0 0 0 0 0 0 0 1 1 0 
7
12
10
9
13
7
15
13
 | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|
0. 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0

1. 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0
     _^ _^                         _^            
2. 1, 2, 2, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0
  _^ _^                      _^                  
3. 2, 2, 2, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0
  _^                      _^                     
4. 2, 2, 2, 1, 2, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0
           _^ _^                      _^         
5. 2, 2, 3, 2, 2, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0
        _^ _^       _^                           
  1. 使用修改右子树的办法时要修改端点
  2. 访问节点信息时要先splay上去,保证懒标之类的发生作用再访问
2024/4/25 10:18
加载中...