harmisyz

摘要： 省流：abc 没质量；cf 没实力。 AT_abc420_f kirinuki 你早说你是 \(O(NM)\) 的不就行了嘛。 一眼感觉不太好计数，但是 \(NM \le 5\times 10^6\) 就很有意思。直接上分治，我们去分治列，则现在只需要解决 \(l_y \in [l,mid]\lan 阅读全文

摘要： 【不会计数，要吐了】 AT_arc174_e Existence Counting 考虑容斥。答案等价于：总的方案数 - 比 \(P\) 大的方案数 - 不包含 \(x\) 的方案数 + 比 \(P\) 大且不包含 \(x\) 的方案数。 第一个东西是 \(A_{n}^k\)，第二个是 \(\sum 阅读全文

摘要： 猫树 概述：类似于 ST表，可以支持快速查询大部分静态区间问题。 实现：考虑将询问分治，对于每次分治到的区间 \([l,r]\)，处理出 \([l,mid]\) 中每个后缀的信息与 \((mid,r]\) 中每个前缀的信息。那么对于一个询问 \([L,R] (L \le mid < R)\)，就可以 阅读全文

摘要： 『我从来没有会过任何串串科技。』 AC 自动机 相当于多个 KMP。也就是多个模板字符串上搞某种匹配问题。 建 AC 自动机 假设我有 \(n\) 个字符串为 \(abc,bcd,bd,c\)（\(n=4\)）。 首先我们对 \(n\) 个字符串建立 Trie 树。长这样：【图】。 如果我们有个匹配 阅读全文

摘要： 『我从来没有会过任何数据结构。』 李超线段树 这玩意是一个可以支持插入直线 \(y=kx+b\)，查询 \(x=x_0\) 时 \(y\) 的最值的数据结构。 很简单，我们记 \(f_x\) 为 \(x_0=x\) 时 \(y\) 的最值对应直线的下标。那么对于插入的一条直线 \(p\)，在位置 \ 阅读全文

摘要： 第一次打省选。 CQ-148，你怎么知道我的考号是倒数第 \(3\) 个。 2025.2.28 住酒店，很唐的。这酒店贵在哪里。350 一晚，感觉和 100 一晚的没区别。 打 div2。开场做 D1，感觉可以打表。然后并没有看出什么明显的规律，结果发现是弱智暴力。切了 A 之后收电脑。rk1400 阅读全文

摘要： 点分治 额，就是你每次去找一棵树的重心，然后将这棵子树变成以这个重心为根的树，再在这个树上进行某些操作，就可以在 \(O(n\log n)\) 的时间复杂度遍历到任意两个点 \(u,v\) 在 \(P(u,v)\) 上某个点 \(x\) 为根时候的贡献了。那么对于类似于求点对 \((u,v)\) 的 阅读全文

摘要： 建议开题顺序：A,B1,B2,C,E,F,D1,D2。 A. Polycarp and Coins 记 \(k=\min(c1,c2)\)，则 \((c1-k)\times 1 +(c2-k)\times 2+k\times 3=n\)。注意到 \(n \mod 3\) 为 \(0,1,2\)。所以 阅读全文

摘要： CF1671E 注意到不同子树间的答案独立。那么对于 \(u\) 为根的子树，其贡献应该是其左儿子乘右儿子再乘它自己的方案。那么由于它自己的方案只与 \(f(l),f(r)\) 有关，所以当其操作后能使答案贡献增加，当且仅当 \(f(l) \ne f(r)\)。为了排除儿子自身的影响，我们将 \(f 阅读全文

摘要： CF1787D 这里有个很典的 trick。我们将 \(i+a_i\) 向 \(i\) 连边，那么只要一个 \(<0\) 或 \(>n\) 的点能够走到 \(i\)，就说明 \(i\) 能在有限的次数内出去。这玩意跑个拓扑排序即可。那么现在我们可以考虑从 \(1\) 开始走，因为只能修改一个点的值， 阅读全文