算法 trick 的记录。 系列前作：https://www.luogu.com.cn/article/yc9w22em 拆贡献！拆贡献！交换维度！交换维度！时间逆流！时间逆流！操作顺序反演！操作顺序反演！递推！递推！分离常量！分离常量！不同的项分开算！ 优化一些代数式计算的复杂度时，最简单常用的技巧就是试着拆开，然后分离常量和变量，将不同类项分开处理。而当你推不出一些式子时，可以放弃推式子而使用递推。交换求和顺序/交换 DP 转移顺序/维度是破解循环依赖，找到好的计算顺序的方法，这和拆贡献是相关的：拆贡献其实就是变换了统计的第一维度。从按照整体的统计变成按照单个元素统计。 双指针就是“在不合法和不优之间的境界线上游走”，同时也是“一种扫描线”，并且是“在复杂度允许的情况下，枚举一定量信息以确定更多条件”的体现。 而“枚举一定量信息”在 DP 中也很常用。DP 的经典套路就是随便乱设状态，加入信息直到能够转移为止，然后利用种种洞察和优化去掉一部分维度，优化转移直到时空复杂度达标。 在做任何题的时候，第一步考虑性质刻画。无论是操作的性质还是维护信息的性质。性质就是限制，能够帮你找出正解。 一个好的性质刻画也很重要。一个愚蠢的性质刻画会极大地妨碍你做题。所以如果你觉得性质刻画太笨，就试着简化。 “信息学”的本质就是对于信息的处理。算法对于复杂度的优化本质上是减少不必要的对信息的处理（计算）。所以当你试图确定复杂度或者优化复杂度时，不妨思考一下“这个题，至少需要处理哪些信息？如何避免处理不必要的信息？” 信息即向量，操作即矩阵。 写了线性代数大学习，你应当能知道这点。有许多操作都是线性/仿射的，可以写成矩阵。从而拥有结合性，可以用快速幂或者线段树等方法处理。 孤链压缩权值线段树/01 trie。线性空间复杂度，从此整数可重集再也不用平衡树。 线性筛线性预处理积性数论函数。要点在于筛 n = i * p 时用到的 p 和 i 满足 p 不大于 i 的最小质因子。比埃筛更好写。 以后再也不要 naive 地 $O(n \log n)$ 算 d(i) 了。 利用单调性等等贪心性质简化问题。 有交不优 => 钦定末尾。 有时二维问题按第一维排序，而后第二维更小就一定更优所以无脑排除一些。剩下的就满足二维偏序（相当于利用贪心性质额外制造了一个维度上的单调性。这里的贪心性质是“a 被 b 包含 => b 的所有解都不劣于 a 的对应解/a 能干的所有 b 都能干”） 两种证明贪心的策略： 局部上，交换论证/调整法：调整一定能导出不劣的解。 整体上，必要性 => 充分性：我们至少需要多少操作，然后让这些操作发挥最大的效益。 增量更新并不要求旧的答案一定是新的答案。在旧答案总数很小时，可以暴力枚举它们判断它们是否是新的答案。或者，如果容易确定哪些不是新的答案，排除它们即可。 对于一些非常复杂的操作，可以考虑寻找不变量。常见的不变量常常和奇偶性或者两类元素的差有关。因为总和是容易变的，但是有时对于两类东西的作用是相同的，就可以被作差消去。 当操作是对两个相邻元素（或者类似的，一个元素附近的几个元素）时，这样的关于奇偶性或者奇偶下标的元素的差的不变量比较容易出现。 不变量和另一种思想紧密相关，即状态而非过程。在很多贪心或者博弈论的题中，常常有复杂的流程模拟，直接陷进去就做不出来了。 这时可以考虑最终状态或者解的性质，有时能够得到非常简洁优雅的结果。就像解方程一样。 ...
聪明与智慧
“聪明”是“硬件”，智慧是软件与算法。
艺术
关于“艺术”。那个经典的问题 艺术的本质是什么？ 我现在知道了答案。 艺术的本质是美。美的传达。 美的本质是感动。 感动将“爱”缔造而出。而爱正是艺术的源头。作者对作品的爱。读者对作品的爱。读者与作者的爱。作品对世界的爱。 爱创造艺术。艺术传递美。美造就感动。感动缔造“爱”。
绝地与西斯
后现代主义教条： 真理是谎言，唯有权力。 通过权力，我获得力量。 通过力量，我获得身份。 通过身份，我获得尊严。 通过尊严，我击碎束缚。 自由将我解放。 古典主义/现代主义教条： 怀疑，然相信。 混乱，然和谐。 激情，然宁静。 愚昧，然求知。 死亡，然真理。
等待
等待吧。等待是最大的美德。 热衷于预测未来的人们，为什么不去请教现实这位最好的推演家呢？
如何研究一个问题？
有一个所谓对象-本质-关系模型：研究一个问题，先找它涉及的要素。再看要素的本质。最后发掘要素间的关系。 立论和驳论同时适用这一套。 三个步骤，每一步都可以注入独特的洞见。也都是驳论的突破口。
一个邪恶的阴谋
用户应当保留拒绝购买任何特定硬件的权利。 用户应当保留拒绝使用任何特定软件的权利。 用户应当保留随时随地登录任何设备的权利。 很可惜，除了密码，没有任何所谓“现代”的安全方案能做到以上三点。 密码学家兜兜转转五十年，发明出一堆原始人都会嘲笑的东西。 邪恶的巨头推广 passkey，推广 2FA，短信验证码，邮箱验证码，要求不能用密码登录……这是一个巨大的阴谋。
一段对话
我给我的妹妹讲课。 （父母出门了） ”你们要什么饮料喝吗？“ ”蜜雪冰城！“ ”不，我不能喝饮料。“ ”哥哥你为什么不喝饮料？“ （父亲）”嗯，你哥哥最近在研究投资。所以他不喝饮料。来，给你妹妹解释一下你在做什么。严肃的讲讲。“ ”好。“ ”你读过《小狗钱钱》吗？“ ”读过。“ ”它在讲什么？“ ”嗯…… 理财？“ ”很好。关于理财，《小狗钱钱》讲了什么？“ ”嗯……“ ”不知道吗。那么，先不管《小狗钱钱》讲了什么，理财是什么？“ ”嗯……合理的安排财产，得到更多钱？“ ”是的。让我总结一下：安排配置财产，用财富追求财富。那么，理财具体在干什么？“ ”额……不知道。“ ”要让我说吗？好吧，理财是投资。而我对投资的理解就是，‘将资金投入再生产’。 ”再问一些问题：财富是什么？资金是什么？钱是什么？资本是什么？“ ”唔……不知道。“ “再想想？” “钱……是一种用来交换东西的……货币？” “太棒了！钱是货币。那么货币是什么？” “不知道……” “货币是货物的象征，也是价值的象征。那么，财富是什么？” “财富是……我拥有的东西，和钱？” “对。物品和钱。货物和货物的象征。财富是价值，是有价值的东西。 “我认为，资金是‘手上的钱’。‘手上的钱’，属于你的，能够支配使用的钱。 ”资本则是生产资料。用于生产的东西。比如，我雇佣工人为我干活，这里我付出的工资就是资本。或者我购买一台机器来生产，那么机器也是资本。 “那么，生产是什么？以及，我们说理财是投资，投资是将资金投入再生产。那么为什么？为什么用财富追求财富，必须将资金投入再生产？ ”或者，告诉我：如何获得财富？“ ”嗯……让我想想……工作可以获得财富？“ ”这是我说的不清楚了。我说的不仅仅是‘个人的获得’。我可以去抢银行，获得财富。但是，财富是如何从无到有，如何被创造出来的呢？我澄清了问题之后，你知道答案了吗？“ ”创造……创造就是创造啊。“ ”那么换个问法：这个过程叫什么呢？给它起个名字？” “生产？” “漂亮！创造财富的过程叫做生产。那么从事生产的过程叫什么？” “劳动？” “太厉害了。从事生产的过程叫劳动。那么你明白为什么理财需要投资了吧？” “明白了。” “同时，投资需要资金。毕竟是‘资金投入再生产’。那么我的资金从哪里来呢？为了节省出这些资金，我不喝饮料。这是节省。“ “接下来，告诉我，要投资，具体可以怎么做？这个社会提供了什么机制，什么手段来投资，把资金投入再生产？” “……我们可以投资一家公司？” ”对的。那么公司是什么？“ ”……“ ”公司是一种人类的组织。那么公司要干什么？或者说，一群人类组织在一起，他们要干什么？“ ”获取财富？“ ”没错！公司是为了获取财富。获取财富需要生产。所以，大部分公司都是为了生产。 ”那么，还是回到最初：具体有哪些手段来投资呢？“ ”不知道。“ “算了，这个你不懂很正常。股票……” “哦！股票！” “不对。金融。投资的手段叫金融。金融的很重要一部分叫做股票。” “这样吗？” “股票就是投资于公司。我们的法律规定了股份制。公司的所有权被切分，然后我们可以购买它的股票。股票是一种凭证，代表公司的所有权。这和国家的货币有点像。 股票能带来分红，也会增值。 “现在明白我在做什么了吧？” “明白了。” “那么今天就到这里吧。我觉得你可能也听不进去更多了。”
CF1903F 题解
原题链接 题解区莫名都使用了线段树优化建图，只有一个人是并查集优化建图，复杂度普遍是 log 平方。 但事实上本题可以容易的做到单 log（二分的 log）。就是使用标题中的科技：K 分块。 其实根本不算科技。非常简单的小技巧。 想必各位还记得 ABC456F 吧？那个题需要维护滑动窗口中不可差分的值（区间 $(\min, +)$ 矩阵积）。 可以使用非删尺取去掉线段树的 log。具体见下文： https://litjohn.pages.dev/posts/2-pointers-with-no-deletion/ 另一种做法就是 K 分块：把序列按照 $k$ 的长度分块，此时发现每个长度为 $k$ 的滑动窗口都恰好覆盖一个块的前缀和一个块的后缀。于是我们维护每个块的前后缀信息，查询时拼起来即可。 看上去没啥用，完全比不上非删尺取。但是在本题中作用就体现出来了：K 分块能够优化建图。 具体的，对于每个块，我们设置一系列节点代表这个块长度为 $x$ 的前/后缀（$x \in [1, k]$）中是否选了点。 然后就是比较套路的建图和 2-SAT 了。题解区已经讲的很明白。 放一下我的提交记录。
Vindows?
何意味了。 一些胡扯。显然我并没有非常深入的实现过操作系统。但下面的东西是一个愿景。 最近爆出了 copy fail 漏洞。触发方式可谓非常简单，代价极小而效力极大。 不禁让人想起了融解/幽灵漏洞（meltdown/spectre）。虽然类型不同，但同样是威胁重大的安全漏洞。 Linux 内核似乎不断地在爆出各种漏洞。一个重要的原因是代码量的庞大。 庞大的代码量必然孕育一些 bug。而且在 Linux kernel 这种规模上，bug 的数量更会超线性增长。原因很简单：已经没有任何人能够完全掌握整个项目的每个细节。 于是，“Tests can only prove the presence of bugs, but never the absence of them.”。 所以，减少漏洞的一个好方法是减少代码量。比如早期 Unix 仅有几千行 C 代码，现在用 rust 可以更少。在如此少的码量中，“眼睛足够多，虫子无处藏”，经过充分的审阅，可以让 bug 几乎被消灭。 更重要的，足够简洁的代码可以动用形式化验证方法。就像 SeL4 那般。 有一种有趣的方法可能实现这一目标。 众所周知，过去的三十年里我们付出了巨大的努力，来欺骗每个应用它们独占一台计算机器。 那么不如做人做到底，给每个应用一台虚拟机。 在这个“Vindows”架构上，机器运行一个 hypervisor。它的代码非常精简，因为 hypervisor 只需要划分资源，而不提供复杂的管理。它提供机制而非策略。 其上运行着许多虚拟机，其中一个拥有特权，名为“管理分区”。 管理分区起到提供策略的作用。它可以与 hypervisor 通信，要求改变资源划分。 其他每个虚拟机中运行着一个定制的微型内核，所谓 unikernel 模式。这个内核的唯一作用是为其中运行的一个应用提供支持。 就像现在的程序语言运行时。 每个应用都以为它运行在完整的一台机器上。 这并非空穴来风。事实上，Azure，GCP，AWS 等云平台已经采用了这样的方案。Windows 在 10 以后也开始采用类似的机制。 优势简单而明显。 首先，安全层面上，这可以防御几乎所有除了侧信道之外的攻击。而且大幅提升侧信道攻击的难度。 其次，这可以降低上下文切换的开销。在这样的系统里，不需要划分 ring0/ring3 权限环。系统调用和普通函数调用一样飞快，昂贵的上下文切换会大大减少。 能够定制专门的文件系统，跑的飞快，同时不受制于 NTFS 这种脑瘫，不需要经过过滤器，不需要审查，也没有杀毒软件。 ...