在文章《题解：AT_arc197_d [ARC197D] Ancestor Relation》发表评论：

哈希+map会带log，哈希+umap可以被卡

通过精细化的实现，其实可以做到 $O(n^2)$ 的复杂度。 首先对于有解的情况，不难发现以下两个性质： 1. 将树根据“分叉点”拆成若干条链，则矩阵中两行相同当且仅当结点在同一条链上； 2. 一条链是另一条链的祖先当且仅当矩阵中对应元素为 $1$ 且前者所在行的 $1$ 的个数大于后者。 根据这两个性质，可以通过矩阵…

在文章《题解：CF2091G Gleb and Boating》发表评论：

复杂度算错了吧，外层调和级数是s+s/2+...+s/k，乘上单次bitset的s/w，是s^2lgk/w，正确的bitset优化应该是移1次2次4次8次这样吧

现有题解好像都带个 $\log$，这里给个线性时间解法。前两种情况用Manacher算法可以直接做到线性，因此主要关注第三种情况。 可以注意到如下性质：**存在某个最长扭动回文串，其 $AB$ 分界线到回文中心的距离等于回文中心在原串中的最长回文半径**。 证明是直观的：任意考虑一个最长扭动回文串，如果它已经满足这一性…

在讨论《站外题求助》回复：

二维差分->二阶差分

在讨论《站外题求助》回复：

首先很容易转化为如下问题：给定数组 $A$，对每个 $k$ 求出 $A$ 中所有长度为 $k$ 的子数组最大值之和。如果对 $k$ 进行枚举，每次需要完整扫一遍数组，时间复杂度过高，因此考虑对每个元素计算贡献。 利用单调栈 $\Theta(n)$ 时间找出每个 $A_i$ 可以作为最大值的区间 $[l,r]$ ，那么只…

### Some notation For an array $A$ of length $n$: - $\min(A)=\min_{i=1}^nA_i$ - $\max(A)=\max_{i=1}^nA_i$ - $L(A,i)=\frac{1}{i}\sum_{k=1}^iA_k$ - $L(A)=\min_{i=…

### 前言 搜了一圈都没有看到对“最小极差等于最大后缀平均值向上取整减去最小前缀平均值向下取整”这一结论的证明，因此在这里补一个。证明过程还是有一定的技巧性的，尤其是引理二，其中用到了一些取整函数的性质，不熟悉的同学可以自行了解。 ### 一些记号 对于长度为 $n$ 的序列 $A$，记： - 下标为 $1\sim…