考虑二分,深度为 mid 是否可行,相当于询问区间中最长的同色段长度是否大于 k.再考虑深度减小对颜色改变的影响,发现可以启发式合并,用线段树维护区间中最长同色段、缀同色段长度、后缀同色段长度.在合并时可持久化.查询时二分即可.在线.时空复杂度都是两只 log.

在讨论《如果考场上只过不了大的样例和拍子怎么办》回复：

小样例都能过（指对拍过大量小数据）而大样例挂了的情况本身就比较少，可能是： - 小样例的情况太普遍，而原题存在特殊数据（如：自环，菊花，贴紧上\下界，可\不可重），可以详细观察数据范围，考虑特殊情况造一些特殊的数据； - 一些代码针对大数据，小数据无法体现正确性（如：大数据可能超过 int，分块时数据小只有一块使跨块的…

在讨论《有关逆序对》回复：

可以考虑dp，从小到大插入数，在不同的位置插能新增若干逆序对数。

在讨论《关于动态开点线段树》回复：

值域大

在讨论《关于 multiset》回复：

正确使用没道理出错。

在讨论《急,求助S组》回复：

我也和你差不多，t1没看出规律。t2细节太多了，调了三个小时都没调出来，导致t3,t4没时间看只好输出随机数。希望 t2 能过 50分。然后 t3,t4 随机出40分我就满意了。 估分只有 90 分，还有一等吗？

在讨论《来个人安慰一下我》回复：

再接再厉，我也没考好。

在讨论《S组T2贪心乱搞有没有hack，民间100》回复：

能否请你简单说说你的思路，一般人应该不太乐意盯代码。

在讨论《求助》回复：

vis导致的。按照你的写法如果要记忆化也得把 vis 放进记忆化的状态里。你可以学习下题解区的写法。

在讨论《关于CSP-S》回复：

你是哪个省的

在讨论《关于spfa》回复：

随机数据下有些确实能优化，但都能卡到nm。

在讨论《这个概率是怎么算的？有点转不过来》回复：

你对状态的定义理解有误。如果 $f_i$ 表示从 $i$ 出发走向终点的概率。从 $i$ 出发有两种选择：走向下一个赌场，概率为 $p_i$；走向上一个赌场，概率为 $1-p_i$。所以转移是：$f_i = p_if_{i+1} + (1-p_i)f_{i-1}$。 至于你说的从 $i-1$ 赌场来的概率是 $p_{i…

在讨论《求问区间加，区间求 k 出现次数，玄关》回复：

@[xxxxxzy](/user/770611) 你想要什么复杂度？

在讨论《启发式合并能用在带权并查集里吗？（不好意思上一次发错了）》回复：

一般的都可以。

在讨论《听灌多》回复：

其实可以 $\Omicron(n+m\log m)$。这是后话。

在讨论《听灌多》回复：

$f_{i,j}$ 表前 $i$ 个数，和为 $j$ 的方案数。 $f_{i,j} = f_{i-1,j} + f_{i-1,j-a_i}$

在讨论《关于最小生成树》回复：

@[zhangbo1000](/user/760291) 要分情况的，应当考虑值域大小。

在讨论《老师给我们布置了一道题，求助》回复：

@[mythic_Magnet](/user/774202) 1~B 的答案减去 1~A-1 的答案

在讨论《关于最小生成树》回复：

完蛋，不会基数排序了，复杂度怎么是 O(n) 的。

在讨论《坐标ZJ，13分能不能过S》回复：

@[cqy12345678](/user/1037709) 我现在也藏起来了。

在讨论《坐标ZJ，13分能不能过S》回复：

违规紫衫

rt，萌新刚学OI，不懂事乱考的。

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[Forg1weN](/user/225515) 请再仔细阅读题面特别是形式化题意部分，可以帮助你理解题意。

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[huanglihuan](/user/794484) 已确认无误

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[_EEA_](/user/533003) 已确认题目描述和形式化题面一致。

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[danlao](/user/1023793) 符合题目要求的spj就会判对，请自行检查是否理解题目要求。

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[Pigeon_cookie](/user/1210103) 不回复做法、写法相关问题

在讨论《「LAOI」Round 6 赛时答疑帖》回复：

@[wwwidk1234](/user/728483) 已确认无误，请再仔细阅读题面。

在讨论《二维数组怎么离散化》回复：

对每一维分别离散

在讨论《关于曼哈顿距离》回复：

@[XP3301_Pipi](/user/1066579) 在图像上相当于是菱形和正方形的转换，即旋转伸缩的线性变换。