[离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解
题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $l...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
[思维+LCT]TopCoder【TreeColoring】题解
题目概述有 $n$ 个点的带边权树和 $m$ 次操作，每次操作：1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。解题报告好像可以大力点分树……我没有想过。考虑我们要求的是 $\sum ...
[LCT+泰勒展开]LOJ2289(THUWC 2017)【在美妙的数学王国中畅游】题解
题目概述有 $n$ 个点，每个点是一个函数：$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作：1.连接 $x,y$ 。2.断开 $x,y$ 。3.修改 $x$ 点函数。4...
[LCT+构造]BZOJ3091【城市旅行】题解
题目概述维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $size$ 倍……把一条路径排成序列，...
[LCT维护最大生成树+二分图判定]BZOJ4025【二分图】题解
题目概述有 $n$ 个点 $m$ 条边，每条边有个出现时间 $s$ 和消失时间 $t$ ，问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示：把边加到线段树里然后线段树二分用LCT判奇...
[分治+LCT+二分图判定]Codeforces19E【Fairy】题解
题目概述有 $n$ 个点 $m$ 条边，问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治，然后用LCT判断有没有奇环就行了。这是斯波做法，时间复杂度 $O(nlog...
