在讨论《LGR-227 赛后总结 & 致歉》回复：

我就qp

在讨论《请问需要训练交互题吗》回复：

需要

首先有一个 $n^2\log n$ 的贪心，我们对于每个 $k$ 从后往前分段，每段的长度尽可能短。这个做法常数很小，但是一个递减序列就把我们卡满了。 首先可以证明我们一共最多有 $\sqrt n$ 种段如果对于两个不同的 $k$，$a$ 为第一个序列的 $a$ 数组，$b$ 为第二个序列的 $a$ 数组 ，有 $a_…

复杂度 $O(q\log n\alpha (c))$。 先说一个 $\log^2$ 的，离线所有询问，树链剖分拆出来所有链。开 $c$ 个平衡树，把每个询问塞到对应答案的平衡树中，在每条链上一边走路一边匹配，当前走到点的权值等于 $p_i$ 那么就将第 $i-1$ 棵树合并到第 $i$ 棵树，需要拿出点时所在树的编号即…

首先可以证明对于所有 $k\ge i$，使 $i$ 取到最大值的位置 $j$ 是不变的，也就是每个值由另外一个位置转移过来，那么另外一个位置在无论 $n$ 取多少的时候都是不变的。 那么只需要枚举这个数的所有因数就可以得到这个数是从哪个位置转移过来的。 观察数据范围发现我们多半不能在线处理询问，而是要预处理出所有答案，…

在文章《题解：P10977 Cut the Sequence》发表评论：

%%%

奇怪的做法。 设当前位置为 $i$，$f_i$ 表示最后一个连续段结尾为 $i$ 的最小答案，开 $10^6$ 个 `multiset` 维护对于每个 $k$,$\displaystyle\max_j^i=k$ 的所有 $f_j$。新加入一个值 $p$ 时将所有 $k using namespace std; #def…

在讨论《洛谷 2 月月赛 I & FTLOI Round 2 赛时答疑》回复：

其余部分用时小于 0.5s

在讨论《洛谷 2 月月赛 I & FTLOI Round 2 赛时答疑》回复：

请问 div1 T1 std 复杂度是否是 $O(n\ln n)$，我预处理每个数的因数跑了 1s。

ix35 的耳分解做法太神仙了，所以介绍一个状压 dp 做法。 最后的答案一定是几个强连通分量加上一些重合的边（2 条边都连接 $u,v$ 则这两条边重合）构成，所以如果我们求出 $f_S$ 表示使点集 $S$ 中所有点强连通的最小花费后可以子集枚举在 $O(3^nm)$ 的复杂度内求出答案。所以我们现在只需要求出 $…

因为是 python 题，所以 c++ 可以爆草，并且现有题解都是 c++ 题解。 首先这题可以二分加哈希得到答案，难点在于如何用哈希判断两串是否是同类串。 因为要解决的是同类串问题，两种字符之间的关系只有相同和不同。我们把每一种字符单独拿出来按所在位置分别哈希得到一个集合，两个串同类当且仅当对应集合相同。 ```cp…

首先可以询问每个字符重复 128 次的串得到答案 $ans$，那么 $ 128-ans $ 就是这个字符在目标串 $T$ 中的出现次数，全部询问完以后 $|T|$ 也可以确定。 编辑距离很不好刻画，于是我们考虑增量法。现在我们已经有一个串 $S$ 是目标串 $T$ 的子序列，我们加入一个字符 $c$，首先想到枚举 $S…

在讨论《不明白为什么 WA》回复：

@[Ascnbeta](luogu://user/767561) 没爆`long long`吗？

感觉此解法不是正解，需要大力卡常才能通过。 树上数颜色想到树分块（设置关键点的那种）。维护到每个关键点每种颜色的出现次数和根到每个关键点的颜色数，查询时暴力向上跳到最近的一个关键点，用关键点的颜色数加上路径上未在根到关键点路径上出现过的颜色数，修改时修改影响到的关键点的颜色数和颜色种类即可。 代码。 ```cpp #i…

转化成每次可以增删一条线段，判断是否满足每条线段都包含或不包含或不相交。 每条线段会出现和消失，想到线段树分治。现在只需要判断每次加入的线段是否满足要求即可。先处理被此线段完全包含的线段。建一颗用于查区间异或值的线段树，每次加入一条线段时将这条线段左右端点的位置都异或上一个随机值。如果 $l,r$ 内的所有线段都被 $…

在讨论《请求修改数据范围》回复：

@[_Kenma_](luogu://user/750163) 有人曾经卡我代码并未成功。

在讨论《请求修改数据范围》回复：

@[_Kenma_](luogu://user/750163) 请给出一组 hack 数据，我试试我的代码（目前最优解）能不能过。

在文章《LZL神话----二南机房惊天之作》发表评论：

这篇文章给我两个 ai 干烧了

在文章《LZL神话----二南机房惊天之作》发表评论：

考虑换个分类

在讨论《求问stable_sort排有序数列时间复杂度》回复：

@[shensiyuan2011](luogu://user/653212) 使用以下代码测试是 $O(n\log n)$。 ```cpp #include using namespace std; const int N = 1e7+100; int a[N],cnt; int main() { for(int i=…

在讨论《求问stable_sort排有序数列时间复杂度》回复：

`stable_sort` 大多情况下都是 $O(n\log n)$，否则就没人用 `sort` 了。@[shensiyuan2011](luogu://user/653212)

在讨论《求问stable_sort排有序数列时间复杂度》回复：

$O(n\log n)$

在讨论《只路径压缩的并查集的最坏复杂度》回复：

最坏 $\log$，均摊 $\alpha$。

在讨论《不理解这么出题有什么意义》回复：

好骂

题解区没看到有这做法的，就发一篇题解吧。 $f_{l,r}$ 表示 $l$ 到 $r$ 全部消除所获得的最大收益，考虑如何处理一个区间 $l,r$。 首先区间最左（或最右）的颜色是可以放到组后消除并不影响答案的，所以我们钦定最后消除这个区间左端点，对于每个区间做一个背包，$g_{r,k}$ 表示最后一次消除的颜色中最后…

在文章《鲜花：详细揭秘：随机选点快速排序的期望复杂度》发表评论：

所以 sort 不是随机化？

在讨论《建议升紫》回复：

@[迟暮天复明](luogu://user/222865) @[Shunpower](luogu://user/399150)

提供一种 $O(n+\log v \alpha(\log v))$ 的做法。 80 分做法同[官解](https://www.luogu.com.cn/article/4v8q67dy)的 80 分。 考虑如何优化，发现可以在一定有两个集合合并时再拆位合并。于是记录每一位所在集合的并，需要时（当前处理的数有一位为 1…

```cpp #include using namespace std; bool v[1000]; vector a[1000]; vector > e; vector tmp; int n,now; mt19937 rd(__builtin_ia32_rdtsc()); inline bool dfs(int x,…

在讨论《建议评黑》回复：

她也没说不会啊。