没翅膀的人与其徒劳描摹天空千遍 不如在诗稿之中离开地面
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
在讨论《时间复杂度里面 /w 是常数吗？》回复：
$w\ge \mathcal O(\log n)$。
在文章《CodeForces Hello 2026 出题记》发表评论：
不烂在哪
在讨论《洛谷 12 月月赛 II & FAOI R10 赛时答疑》回复：
请问 H 中字符串只包含小写英文字母吗
 把静态 Top Tree 建出来，每个节点维护加常量加到上界点的距离加到下界点的距离三个标记，子树加和子树补加都可以直接搜，容…
很久以前，吃饭给了我一个神秘 $m-n=20$ 题，做法是，点集可达点的交只有 $\mathcal O(n+2^{m-n})$ 种。 吃饭说，他证出了只有 $\mathcal O(2^{\sqrt{m-n}})$ 个有用的，所以 $m-n$ 可以很大，于是我去睡觉了。可惜我睡了一半发现可以优化建图，于是有了西安站 D…
考虑这样一类问题：有一个序列 $a_{1\dots n}$，每次询问一个区间建出来的笛卡尔树上的一些事情。 不妨假设 $a_i$ 互不相同，我们需要的是大根笛卡尔树。考虑怎么刻画一个区间 $[l,r]$ 的笛卡尔树： - 首先根是区间最大值：$p_0=\arg\max\limits_{i\in[l,r]}a_i$。 -…
在文章《【欢迎投稿】有奖征集 OI 小知识点，思考题和科普，包括“广为人知”但大纲未收录的内容！》发表评论：
已投稿 https://www.luogu.com.cn/article/tunopx0i
前置知识：[树链剖分](https://oi-wiki.org/graph/hld/) ## 全局平衡二叉树 考虑这样一个问题： - 有一棵 $n$ 个节点的树，需要支持两种操作： - 给 $1\sim x$ 路径上每个节点权值 $+y$； - 求 $1\sim x$ 路径上每个节点权值之和。 一个常见的解法是树链剖分…
## A $0,1,0,1,1,0,1$ 卷积 $n$ 次的结果，直接 NTT 快速幂。$O(n \log n)$。 ## B 枚举 $a,b$，根据题意直接设计 DP $f_i=f_{i-2},g_i=f_{i-3}+g_{i-3}$，矩阵快速幂优化。$O(\log n)$。 ## C 容斥，钦定 $i$ 个数大于…
问题转化为每个数有 $[1,2][3,4]$ 和 $[1,3][2,4]$ 两种情况，然后有包含关系的连边 2-sat。 我们先不急着优化建图。考虑使用 kosaraju 求 SCC，我们只需要在原图和反图上模拟 DFS，也就是需要每次找到一个和某个区间有包含关系且没访问过的点。 假如我们现在的区间是 $[l,r]$，…
这个题可以单 $\log$。 [前面忘了。](https://www.luogu.com.cn/article/pirnw2ib) 默认大家会 $\log^3$ 做法。考虑我们是怎么加入一个元素的：把他加入某个数据结构，然后找到最深的子树内元素个数大于子树大小的节点，删除子树内最小的元素。 注意到我们只修改了两个元素，…
我将详细揭秘这为什么是一个难度适中的 CSP 模拟赛的题。 为了方便我们 $a_i\gets m-a_i$。 我们从左往右扫，维护一些区间 $[0,x]$ 表示将这个区间的值 $+1$。对于一个需要 $-1$ 的区间 $(y,m]$，如果 $x>y$ 那么我们可以交换 $x,y$。那么对于所有区间操作一遍就相当于把 $…
在讨论《高二学生，CSPS 初赛在即，求各位大佬提点建议！》回复：
你咋这么可爱
## A 考虑根被插入的时间，在根被插入之前的数都会放到同一个儿子，插入之后的数会交替往两边插入，形式一定形如 $\texttt{LLLLXRLRL}$ 或 $\texttt{RRRRXLRLRL}$，这样我们就递归到了儿子的子问题。合并的时候分类讨论一下 $sz_{ls}$ 和 $sz_{rs}$ 的大小关系，暴力合…
在文章《解决 Dynamic Rankings，但是用在线 polylog 算法做到 O(n) 空间》发表评论：
为啥需要再写一个 fhq，你删点的时候显然知道他是什么啊（）
首先我们阅读 Purslane 大神的题解得知，集合幂级数 exp 的意思是 $b_S=\sum\limits_{S_1\cup\dots\cup S_k=S,|S_1|+\dots+|S_k|=|S|}\prod\limits_{i=1}^ka_{S_i}$。 我们容易写出 $b_S=\sum\limits_{T\s…
纯纯意义不明弱智题，但是严肃被通信正义击杀了。 从 $T$ 中随便拿一个排列 $q$，考虑设 $f_{i,j,k}$ 表示 $q$ 只考虑 $[i,j]$ 和 $[k,n]$ 的方案数，转移就是拓展 $i-1$ 或者 $k-1$，然后在其他 $T$ 中元素中这些数对应位置也需要一直维持类似的结构。但是可能出现在某个 $…
我咋这么唐呢。 首先有一个自然的想法是，取出一个生成树，想一个比较好看的树的构造，然后每个节点额外塞一些非树边。 树的情况考虑这样的构造： \to(x,a)\to(x,b)\to(0,b)$。设一列中第一个空的位置是 $fi_i$，前缀连续空的长度是 $cn_i$，$a\to b$ 之间的 $\max H$ 位置为 $c$，那能这么走就相当于…
模拟赛场上想出来的神秘做法。 对于单组询问，我们考虑在笛卡尔树上 DP，显然有转移： $$f_u=\min(f_{ls_u}+a_u(sz_{rs_u}+1),f_{rs_u}+a_u(sz_{ls_u}+1))$$ 考虑怎么刻画区间笛卡尔树：找到区间最大值，把从左端点开始的前缀 $\max$ 及其右儿子和从右端点开始…
在文章《P4298 [CTSC2008] 祭祀 题解》发表评论：
真是太牛了! ! ! 我对您的景仰如高山流水般连绵不绝 , 您的光芒万丈荡去了我内心的黑暗 , 您是我偶像啊! ! ! !
为什么是倍增？ 首先我们显然可以加一个随机的巨大数字，这样只要让相同的数不能被相同的区间覆盖到即可。然后考虑 $l$ 和 $r+1$ 构成的可重集，如果我们将前一半和后一半依次配对，这样对于每个数只要相邻两次出现之间有至少一个端点且第一次出现前和最后一次出现后至少有一个端点就满足了要求，显然这样是最优的。 现在问题就变…
考虑二分，检查是否有 $\ge len$ 的公共匹配串。 对于一个匹配串，设左括号为 $1$ 右括号为 $-1$，那么所有后缀和为 $0$ 的后缀都是匹配串，我们就截取最短的 $\ge len$ 的后缀。这样我们只需要从两个串中分别拿出每个右端点往左最短的 $\ge len$ 的合法后缀的哈希，检查是否有交即可。求这些…
在讨论《LGR-225 赛后总结帖》回复：
嘟嘟嘟
设 $b_i=\max(a_i,a_{i+1})$，考虑在 $b$ 上操作，每次操作就是删掉一个数 $x$ 并且两侧都对 $x+1$ 取 $\max$。然后肯定是删最小的影响最小，考虑一个长度为 $l$ 的最小值 $x$ 的连续段，至少会操作出 $\lfloor \frac l 2 \rfloor$ 个 $x+1$。然…
如果 $y=0$ 那显然是排好序之后相邻的匹配，$y\le 1$ 显然也不能有在横坐标上有交的对，且答案最多比不考虑纵坐标的答案多 $1$。我们只要检查能否通过重排每个横坐标内部的顺序得到 $y=0$ 时的答案 $lim$。 首先判掉每个横坐标内部都可以全部匹配的情况。考虑 DP，设 $f_{i,0/1}$ 表示考虑第…
考虑如果需要回答的是最大怎么做。维护一个单调栈，加入一个点的时候询问当前栈顶 $j$ 到新元素 $i$ 这段区间，如果 $p_j p_i$ 次大就变成 $i$ 了，存下每个位置的单调栈就可以用 $2n$ 次询问回答出最大的问题。 然后考虑拓展一下这个单调栈，把所有会更新次大的元素也加入。称更新最大的元素为第一类，更新次…
神奇 trick。 在 DFS 序上 DP，设 $f_{i,j}$ 为 DFS 序在 $[1,i)$ 中的点代价为 $j$ 的答案。选 $i$ 这个点就转移到 $i+1$，不选就转移到 $end_i+1$（即这个子树外）。 ```cpp rep(i,1,n){ int u=rdfn[i]; rep(j,0,m){ ch…
在讨论《（有偿）求题单》回复：
我也想要/kel