ARC138E Decreasing Subsequence 第一步是巧妙的转化：对于 $a_i>0$，连边 $(i,a_i-1)$。 对于每个序列 $a$，连边后形成若干条链。 假设选出的 $k$ 个点为 $b_1,b_2,…,b_k$，并且 $b_1<b_2<…<b_k$，对应的 $a_{b_1}-1,…,a_{b_k}-1$ 为了方便记作 $c_1,c_2,…,c_k$，则有： $$c_k<c_{k-1}<…< 2022-04-11 题解 图论模型 第二类斯特林数
「联合省选 2020 A」组合数问题 之前以为是我不会的科技题，没想到是勾巴题（（ 观察到多项式次数 $m\le 1e3$，考虑计算每项的贡献： $$\sum\limits_{i=0}^m a_i\sum\limits_{k=0}^n k^i x^k \dbinom n k$$ 将 $k^i$ 用第二类斯特林数换掉： $$\sum\limits_{i=0}^m a_i\sum\limits_{k=0}^nx^k\dbinom n k\ 2022-03-24 题解 斯特林数 二项式定理
CF1017G The Tree $\text{link}$ 对于询问 $\text{3 x}$ ，若操作 $\text{1 y}$ 使得 $x$ 染上了黑色，那么满足 $y$ 是 $x$ 的祖先并且 $y\longrightarrow$ 路径上操作 $1$ 的个数 $\ge$ 路径上的总点数（包括 $x,y$）。 考虑给每个点附一个权值 $-1$ ，操作 $\text{1 x}$ 则对 $x$ 单点 $+1$，那么查询时只需要判 2022-03-17 题解 树链剖分 线段树
莫队二次离线学习笔记 例题$\texttt{Luogu P4887 [模板]莫队二次离线}$ 设莫队指针移动时间复杂度为 $O(k)$ ，则普通莫队的时间复杂度为 $O(m\sqrt n k)$ ，使用莫队二次离线可以变成 $O(m\sqrt n + nk)$ 。 本题直接莫队做是 $O(m\sqrt n\binom{14}{k})$ 的，无法通过。 记 $a_x$ 对区间 $[l,r]$ 的贡献为 $f(x,[l,r 2022-03-17 学习笔记
群论学习笔记 参考资料： command_block’s blog 群的概念及基本性质 由集合 $G\neq \emptyset$ 和 $G$ 上的二元运算 $*$ 组成。 满足以下性质： 封闭性：$\forall a,b\in G,$ 均有 $(a*b)\in G$。 结合律：$(a*b)*c=a*(b*c)$ 。 存在单位元：存在 $\epsilon\in G$ 使得 $\forall a\in 2022-03-16 学习笔记
CF1109F Sasha and Algorithm of Silence's Sounds $\text{link}$ 首先考虑计算每个左端点对应的合法右端点的个数，可以发现随着 $l$ 的增大，使得 $[l,r]$ 不存在环的最大的 $r$ 是单调递增的，然后我就不会了。。。 看了题解才想起来可以利用树“点数-边数=1”的性质计算，于是拿棵线段树顺便维护一下“点数-边数”的最小值以及最小值的个数就好了，因为 $[l,l]$ 显然满足 “点数-边数=1” 。 时间复杂度 $\mathrm 2022-03-16 题解 线段树 LCT Two Pointers
CF232E Quick Tortoise $\text{link}$ 先将询问离线下来分治，设当前分治区间为 $[l,r]$ , $mid = (l + r) >> 1$，考虑处理左上角到右下角的询问，剩下的分到左右两边。 由于路径必然经过 $y=mid$ 这条直线，考虑记 $g1(i,j,k) = 1/0$ 表示 $(i,j)$ 能否走到 $(k,mid)$， $g2(i,j,k) = 1/0$ 表示 $(k,mid)$ 能 2022-03-15 题解 分治 bitset
「雅礼集训 2018 Day7」A $\text{link}$ 用线段树维护 $\text{And,Or,Min}$ 值，对于操作： $\text{And x}$，设当前点为 $u$，区间值分别为 $ta(u),to(u),tm(u)$： 若 $x \And to(u) = to(u)$ ,则该操作对当前区间 $[l(u),r(u)]$ 的值无效； 若 $to(u) \And x = ta(u) \And x$ ,则该操作对当 2022-03-15 题解 线段树 势能分析