lct题单

本题单详细整理了lct的各种应用，各种模型，并且题目众多，选择丰富 每一类基本按照难度排序 ## 一 P2147~P4546 lct的基础应用，其中有些也可以用树剖实现，不过lct代码简单，且理论复杂度更优秀 其中P4546结合了泰勒展开与多项式相关，需要一定的数学基础，谨慎食用 ## 二 P2387~P3206 lct维护最小生成树 P4319和P3206需要线段树分治辅助 ## 三 P3703~CF1137F 树点涂色模型 除了access并没用到lct的其他函数，只是题目要求实现的与access操作类似，因此可以用lct维护 ## 四 P5227~P5247 图的连通性相关，其中P5247谨慎食用 ## 五 P5489~P2542 lct维护边双/圆方树 ## 六 P5212~P3785 与字符串的结合，用lct维护后缀树 ## 七 P5385~CF1386C 区间的lct 可能需要配合一些分治结构 如线段树分治和整体二分 ## 八 P4219~P5526 lct维护子树信息，后面两道题可以量力而行 ## 九 P3203~CF1039E lct把一个序列变成一棵树，并动态维护 ## 十 P4751~P3781 动态dp的实现方法之一，不过更建议写全局平衡树二叉树 P5649 sone1 lct的综合题，可以说是最难的了