Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SDOI2008」洞穴勘测 - Link-Cut Tree

    如果监测到洞穴 u u 和洞穴 v v 之间出现了一条通道,终端机上会显示一条指令 Connect u v;如果监测到洞穴 u u 和洞穴 v v 之间的通道被毁,终端机上会显示一条指令 Destroy u v。辉辉希望能随时通过终端机发出指令 Query u v,向监测仪询问此时洞穴 u u 和洞穴 v v 是否连通。已知在第一条指令显示之前,洞穴群中没有任何通道存在。

    于  BZOJ, CodeVS, Link-Cut Tree, SDOI, 动态树, 数据结构, 高级数据结构 继续阅读

  2. Link-Cut Tree 学习笔记

    Link-Cut Tree 是一种用来维护动态森林连通性的数据结构,适用于动态树问题。它采用类似树链剖分的轻重边路径剖分,把树边分为实边和虚边,并用 Splay 来维护每一条实路径。Link-Cut Tree 的基本操作复杂度为均摊 O(logn)O({\log}n),但常数因子较大,一般效率会低于树链剖分。

    于  Link-Cut Tree, Splay, 动态树, 数据结构, 算法模板, 高级数据结构 继续阅读