LCT维护一个森林，即把每个节点用splay维护，可以进行许多操作： 查询、修改链上的信息 随意指定原树的根（即换根） 动态连边、删边 合并两棵树、分离一棵树 动态维护连通性 等 主要性质 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。 每个节点仅包含于一个splay中。 边分为实边和虚边...

P5350 序列 题意 维护一个序列，支持区间求和、赋值、加值、复制、交换、翻转操作，其中交换和复制操作保证两段区间长度相等且不交。答案对 \(1e9+7\) 取模。 思路 对于区间求和、赋值、加值、交换、翻转操作我们都可以很轻松地使用平衡树进行维护。所以现在的难点就在于复制操作：如何复制一段区间？ 如果我们暴力复制的话，每次我们不得不将被复制的子树扫一遍进行复制，这是肯定不行的...

P6106 [Ynoi2010] Self Adjusting Top Tree 题意 给出平面直角坐标系上若干不与坐标轴平行的处于第一象限的互不相交的线段，多次询问平面中一个第一象限的矩形与这些线段相交部分的长度长度和与所有线段长度和的比值。给出的所有坐标 \(\in[1,10^6]\)。 思路 假设所有线段的斜率都是正的，考虑将询问差分成四个前缀矩形。我们只需要考虑统计若干斜...