LuoguLOJ分析将每个格点拆成四个点,分别表示从这个点往右走、往下走、往左走、往上走。对每个点维护一个 $nxt$,表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环,我们想办法对其进行维护。考虑将环拆掉一条边变成一条有向链,并用 LCT 维护这条链。我们同时维护每一段墙是否存在,并修改连进某个点的链。在修改时,我们首先断掉连进来的边,然后再根据墙的情况修改...
CodeforcesLuogu分析考虑计算每种颜色的贡献,即计算每种颜色包含在多少条路径中。这个东西似乎还是不好算,可以考虑计算每种颜色不包含在多少条路径中。我们把这种颜色染成白色,其它颜色染成黑色,那么只有黑色连通块内部的点对才满足条件。于是我们需要支持修改颜色、求黑色连通块大小平方和,使用 QTREE6 一题的方法把颜色放到父边上,LCT 维护子树信息即可。具体细节可以看一看官方题解中的...
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来,然后树状数组求逆序对数,再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的,所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
SPOJLuogu分析首先思路肯定就是建 SAM,询问就找到对应位置然后求 $size$。然而我们要支持插入,也就是要动态维护 $size$。可以用 LCT 维护 Parent 树,每次相当于求子树和,用维护子树信息那一套即可。当然也可以直接链修改。代码我的写法可能有点奇怪 /kel// ==================================== // author: M_...
LuoguLOJ分析可以发现每种颜色一定是一条链,则整棵树相当于被剖分成了若干条链。考虑 LCT 维护,则 1 操作相当于 access(x),2 操作相当于询问一条路径上的链数,3 操作相当于求子树中到根路径上链数最大的点。考虑将 2 操作差分,则只需要用一个数据结构维护每个点到根路径的链数,要求支持区间求最大值。考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x...
LOJ分析根据一个结论可以知道,距离树上一点最远的点一定是直径的两个端点之一。于是可以用并查集维护连通块,同时维护每个连通块的直径的端点,合并两个连通块时在六条可能的直径中取个 $\max$ 即可。需要支持加边和询问两点间距离,可以用 LCT 实现。代码// ==================================== // author: M_sea // web...
CodeforcesLuogu分析首先有一个结论:一个大小为偶数的连通块一定存在一个合法的边集,一个大小为奇数的连通块一定不存在一个合法的边集。证明:如果连通块大小为奇数,又因为每个点度数都为奇数,所以总度数为奇数,这是不可能的。如果连通块大小为偶数,此时我们可以先找到一棵生成树,从下往上构造即可。可以发现一定能构造出解。于是我们只需要保证图中没有大小为奇数的连通块即可。考虑一个类似 Kru...
QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权,然后就是个树剖板子了...但是注意查询时 LCA 是不能查的,需要判一下。而且这题竟然不能交 C++ ,然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上,然后倍增上去即可求出。所以只...
LuoguLOJ分析动态 DP 。我们要求的是最小点覆盖,这个东西就等于权值和减去最大权独立集。那么就是差不多就是【模板】动态DP了。强制选的话,就把权值改成 $\infty$ ;强制不选的话,就把权值改成 $-\infty$ 。然后就做完了。代码// =================================== // author: M_sea // website: h...
PJ标题统计按照题意模拟即可。龙虎斗枚举即可。记得开 $\texttt{long long}$ 。摆渡车设 $f[i]$ 表示前 $i$ 时刻的答案,容易得到 $\displaystyle f[i]=\min_{j\leq i-m}\{f[j]+\sum_{j<k\leq i}i-t_k\}$ 。直接前缀和优化即可得到 $50$ 分。考虑优化。可以发现 $j$ 只需要从 $i-2m+1...