更好的阅读体验\Huge 更好的阅读体验更好的阅读体验 请注意，由于本文 markdown 源码达到了 400K，页面渲染较慢是正常现象，请耐心等待。 本文共 33.1w 字符，1.2w 行，200 道例题，完整阅读大概需要 6.5h。 0. 前言 为什么要写这篇文章呢？因为教练让我们选一个专题写博客然后交流。 为什么选数学呢？因为线段树分块都被选走了，而数学专题没人选，并且可以把写过的笔记拼

这里记录一些做题时学到的结论 & 套路 & 注意事项。 区间 [l,r][l,r][l,r] 内的下标 xxx 在该区间翻转后的下标是 l+r−xl+r-xl+r−x。 维护 010101 序列的时候，可以维护所有 0/10/10/1 的下标。 一个数 v≥1v \ge 1v≥1 在 O(log⁡log⁡v)O(\log \log v)O(loglogv) 次开方下取整后变为 1

“铲雪”类问题出自本人的模拟赛，这类题目的一般形式如：给你序列 aaa，一次操作将一个特定结构中所有元素减 111，求元素全变成 000 的最少操作数。 本文可能并不会给出严谨的正确性证明，更多的是叙述做法。 序列版本 给你长度为 nnn 的数组 aaa。一次操作将一个子区间上所有元素减 111。 求元素全变成 000 的最少操作数。 n≤105,ai≥0n \le 10^5, a_i \ge

月考完就停课了，冲 NOIP。希望明年能进队吧。 Day 1 10.13。第一节语文。前面大题怎么这么不难，写写写。作文怎么这么困难，写写写。写完自己都不想读。自我评价是前面成功了，作文失败了。 第二节地理。20min 写完以后开始 Sleep。睡了 15min 起来没意思，开始默写排列组合、Catalan 数、Striling 数，然后手推了一下斐波那契生成函数的封闭形式。 下午，第三节数学。单

做题记录。二次离线莫队科技。 给你一个长为 nnn 的序列 aaa，qqq 次询问，每次查询一个区间的逆序对数。 n,q≤105n, q\le 10^5n,q≤105。 下文复杂度分析认为 n,qn,qn,q 同阶。先离散化。 考虑普通莫队怎么做。我们开一个权值树状数组，每次指针移动时在值域上查询有多少个数比它小。复杂度 O(nnlog⁡n)O(n\sqrt{n} \log n)O(nn​lo

原理 dsu on tree 是一种人类智慧的做法，用来处理一类子树信息的问题。下面来个例题： 给你一棵大小为 nnn 的树，每个节点有颜色 cuc_ucu​。qqq 次询问，每次询问以 uuu 为根的子树中的颜色数。 n,q≤105n,q \le 10^5n,q≤105。 首先和重链剖分一样，记 szusz_uszu​ 为子树大小，定义重儿子为 szvsz_vszv​ 最大的节点，轻儿子为其

你是否有过这样的经历：出完一个题，写好了 std 和 maker，然后上讨论区求助“求生成数据模板”…… 你是否有过这样的经历：出了一道图论题，图要卡掉 SPFA。用 C++ 写了 114514114514114514 小时…… 如果你有以上困扰的话，那么欢迎使用 KittenGen。 KittenGen 是什么 一个基于 Python3 的 Flask 框架搭建的本地化数据生成器。在运行时，它将

之前我写过一篇文章：浅谈一种黑科技——索引树优化块状链表，说人话就是对于每个块的长度建一棵线段树。 今天去 P6136 看了一下，怎么有高手卡到 2.5s 了？ 翻了下代码，发现最大的改变就是把线段树变成了树状数组。于是花 eps 时间实现了这个东西，又花 eps 时间写了一个对读入分块的 extend 函数，交上去，不是怎么 2.7s。 换成 C++20，这下 2.52s 了。 原理 考虑一下普

由于本人在 9.26 模拟赛中的 T2 二十分钟瞪出了做法，然后自己否掉导致写了 2h 喜提 240pts，故对这类题目作一个总结。 AT_abc195_f [ABC195F] Coprime Present 这题就是本人模拟赛的那个 T2。 ::::success[题解] 一个思路是注意到最大答案在 2×1082 \times 10^82×108 左右，可以进行 O(ans)O(ans)O(an

这部分内容摘自 OI 中的数学基础中组合数学部分，将并入之后更新的第二版内容。 OI 中的数学基础の洛谷链接。 如果某些计数问题的限制是“某些物品恰好若干个”，就可以考虑使用二项式反演。 原理 设 fnf_nfn​ 表示恰好使用 nnn 个不同元素形成特定结构的方案数，gng_ngn​ 表示从这 nnn 个不同元素中选出若干个元素形成特定结构的方案数。 已知 fnf_nfn​ 求 gng_ngn​