洛谷4747 [CERC2017]Intrinsic Interval
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
标签 ST 表 下的文章
- 首页
- ST 表
洛谷5503 [JSOI2016]灯塔
Luogu分析一个决策单调性做法移一下项发现我们要对每个 $i$ 求出显然 $\left\lceil\sqrt{|i-j|}\right\rceil$ 的取值只有 $\mathcal{O}(\sqrt{n})$ 级别，可以枚举它的取值，用 ST 表求出对应区间的最大值即可。代码// =================================== // author: M_sea ...
洛谷6087 [JSOI2015]送礼物
Luogu分析先把长度为 $L$ 时的答案算出来，则剩下的情况中仅有最小值、最大值分别在两端点的区间可能成为答案。为了方便，只考虑最小值在左端点的情况，另一种情况类似。既然是分数规划，二分答案 $mid$，check() 时需要判定单调队列求出左边的最大值即可。代码// =================================== // author: M_sea // w...
CF1004E Sonya and Ice Cream
CodeforcesLuogu分析显然选的路径是直径的一部分。为了方便，把直径上的点重编号为 $1\sim cnt$。我们把这棵树想象成一条链上挂了一些子树。那么设一个 $maxdis_i$ 表示 $i$ 子树中到 $i$ 最远的点的距离。一个暴力做法是枚举选的路径 $[l,r]$，此时最大距离就是 $1\sim l$ 的距离、$r\sim cnt$ 的距离、$\max_{i=l}^r\le...
CF1142B Lynyrd Skynyrd
CodeforcesLuogu分析我写个倍增都能写自闭...考虑你选了一个数之后，下一个数是唯一确定的，而且肯定越靠前越好。设 $nxt_i$ 表示选了 $a_i$ 之后下一个数选哪个。特别的，如果不存在能选的下一个数，$nxt_i=\infty$。那么我们就相当于要询问 $[l,r]$ 中是否存在一个 $i$ 满足跳 $n-1$ 次 $nxt$ 后跳到的数还在 $[l,r]$ 中。倍增预处...
Educational Codeforces Round 69 题解
比赛地址我真的什么都不会了嘤嘤嘤DIY Wooden Ladder语文题设次大的 $a$ 为 $x$ 。那么显然答案为 $\min\left\{n-2,x-1\right\}$ 。代码Pillars从大到小考虑所有盘子，如果它到最大的那个盘子中没有比它小的就可以移过去。写一个 ST 表 / 线段树 / 平衡树 / 分块 / …… 求区间最小值即可。代码Array Splitting假设分成两...
洛谷2471 [SCOI2007]降雨量
LuoguBZOJ分析用$\texttt{ST表}$来维护区间最大值。将年份离散化，对每个查询分四种情况讨论。细节见代码内的注释。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #incl...
洛谷2216 [HAOI2007]理想的正方形
LuoguBZOJ分析直接上二维$\texttt{ST}$表。预处理是$O(n^2\,\log^2\,n)$的，枚举+查询是$O(n^2)$的。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring>...