洛谷5891 Fracture Ray
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
标签 线段树 下的文章
- 首页
- 线段树
洛谷4770 [NOI2018]你的名字
LuoguLOJ分析先考虑 $l=1,r=|S|$ 的情况。对 $S$ 和 $T$ 建 SAM。设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出：如果有对应的转移直接走过去，匹配长度加 $1$；否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$；如果跳到 $1$ 都没有...
洛谷3707 [SDOI2017]相关分析
LuoguLOJ分析前两个用平方和公式求，后两个用等差数列求和求，并打一个赋值标记即可。实现起来细节比较多。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #inc...
洛谷4364 [九省联考2018]IIIDX
LuoguLOJ分析把所有难度从大到小排序，然后从小到大给每个节点选一个难度。对于每个节点，我们至少要保证未选的难度中有 $sz$ 个 $\geq$ 它选的难度。设 $f_i$ 表示 $[1,i]$ 中有多少个难度可以填，则所有满足 $\min_{j=i}^n\{f_j\}\geq sz$ 的难度 $i$ 都可以被当前节点选择。显然我们选最靠右的位置会最优。假设这个位置是 $p$，则我们需要...
CF487E Tourists
CodeforcesLuogu分析可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修...
洛谷3703 [SDOI2017]树点涂色
LuoguLOJ分析可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x...
CF1063F String Journey
CodeforcesLuogu分析为了方便，把串翻转，条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。可以发现一个性质，即在一定存在一组最优解使得 $|t_i|=i$，因为某个不满足的串删去多的部分一定不会差。于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-1}\geq...
LOJ3280 「JOISC 2020 Day4」首都城市
LOJ分析考虑建一个图，即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点，则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通，则必须把 $u,v$ 合并。考虑一个强连通分量，显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并，因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
LOJ3282 「JOISC 2020 Day4」治疗计划
LOJ分析考虑两个方案 $[L_i,R_i]$ 和 $[L_j,R_j]$ 先后执行后能否合并为一个健康人区间。显然应该满足因此我们可以以任意顺序加入方案，最后合并成 $[1,n]$ 即可。所以可以从左往右考虑。考虑最短路，将所有 $L_i=1$ 的点作为源点，如果 $i,j$ 能合并则从 $i$ 向 $j$ 连边 $c_j$。然而需要优化。把绝对值拆开：如果 $T_i\geq T_j$，则...
CF1270H Number of Components
CodeforcesLuogu分析可以发现一个性质，即连通块一定是连续的一段。证明可以设 $i<k<j$，然后讨论各种情况，并证明无论如何 $k$ 与 $i,j$ 都连通。证起来有些复杂所以此处略去（那么我们可以枚举连通块的最右边的点 $p$，如果 $[1,p]$ 与 $[p+1,n]$ 间没有连边即 $\min_{1\leq i\leq p}a_\max_{p+1\leq i\...