原题链接 题解区莫名都使用了线段树优化建图，只有一个人是并查集优化建图，复杂度普遍是 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 了。题解区已经讲的很明白。 放一下我的提交记录。

何意味了。 一些胡扯。显然我并没有非常深入的实现过操作系统。但下面的东西是一个愿景。 最近爆出了 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 这种脑瘫，不需要经过过滤器，不需要审查，也没有杀毒软件。 ...

久仰大名。我曾经看某几位大佬的文章了解到这种算法的存在，但一直没有去学。 在 ABC456F 用到了这个算法，于是简单介绍。 简介 双指针是常用的算法，一个用途是维护滑动窗口内的某种答案，如窗口内的区间最大值。 但一般要求操作可逆。因为我们需要将一些东西移出区间，必须消除它们对记录的答案的影响。 如果操作满足结合律，有时我们可以不使用删除而完成双指针。通过定期完全重构区间答案。 队列 无论目的为何，双指针的滑动窗口总是可以视为一个队列：右边指针右移就是将下一个元素入队，左边指针右移就是将最早加入的元素出队。 我们考虑使用两个栈 s1 和 s2 维护这个队列：加入一个元素时直接加入 s2，弹出一个元素时如果 s1 非空，直接弹出 s1 栈顶；否则我们进行一轮重构： 将 s2 的每个元素依次取出（按从栈顶到栈底的顺序）并压入 s1 的栈顶。 容易证明复杂度是线性的。具体的：每个元素最多入栈两次，出栈两次。 计算答案 仅仅是这样一个奇怪的队列并无用处。但是这个过程中我们可以维护区间信息。 假设我们维护的是从左到右的区间信息，即如果我们的区间是 $[l, r]$，我们要求的是 $\operatorname{op}(a_l, a_{l+1}, \cdots, a_r)$。 对于 s2，我们对其中每个元素维护栈底到它的前缀答案。 对于 s1，刚好反过来：对每个元素维护它到栈底的前缀答案。 说的有点抽象，画个图： 1 2 3 4 5 6 7 8 栈底 栈顶 s1: [a, b, c, d, ...] | 维护 op(b, a) s2: [A, B, C, D, ...] | 维护 op(A, B, C) 这样，我们将 s1 与 s2 的栈顶的信息合并起来即可得到区间信息。 ...

西电校赛遇到的神秘题目。 题目 称长度为 $n$ 的排列 $p$ 是完美的，当且仅当对于任意 $1 \leq i < j \leq n$，$p_i \perp p_j$ 当且仅当 $i \perp j$（这里的垂直符号代表互素）。 给定正整数 $n$ 满足 $n \leq 10^6$，请求出长度为 $n$ 的完美的排列的总数，对 $10^9+7$ 取模。 初步思考 注意到恒等排列 $p_i \equiv i$ 一定合法。 考虑用交换构造出所有排列。什么交换是不合法的呢？ 对于两个位置 $i, j$，如果有另一个位置 $k$ 与 $i$ 不互素而与 $j$ 互素，或反之（即 $k$ 与 $i$ 和 $j$ 的互素性不同），则称 $k$ 是能区分 $i$ 和 $j$ 的一个证人。 如果 $i$ 和 $j$ 有证人，则我们不能随意交换它们，否则与那个证人之间的互素关系就会发生变化。 反之，我们可以任意交换放在这两个位置上的数。 我们称两个位置没有证人为“同类”。注意到这个关系具备传递性，从而是等价关系。 那么这些位置上能放的数字就是相同的集合，可以任意排列。 刻画同类关系。注意到两个数是同类，当且仅当它们的质因子集合是相同的。 于是不难想到用无平方因子数作为一类数的代表元。线性筛预处理每个位置的代表元。 预处理阶乘。 发现有另一类可能的变换：对于大于 $n/2$ 的素数，能区分它们和其他数的证人太大，所以这些数以及 1 之间是同类的。 ...

你似那春日晴风 闭眸在余霞夕暮 心绪正寄向何方？ 睁开眼 双目剔透如琉璃 依稀有丝晴日气息 白日晴空/予花绽 百花不过/因晴开 纵使雨过天晴 可连草露雨滴 也将乔饰你的晴空 待心中浪涛平如镜 我们亦化作晴风 将那朵云彩也跨越 直到吹至天际彼方 你似那晴日徐风 闭眸又若晴蓝天空 眉宇间，何以染了轻愁？ 待我睁开双目 你双眸似琉璃 如今却嗅到一丝阴雨 泪痕见湿 天同泣 落泪亦作 雨自咎 纵使天不作美 可算阴雨连绵 云上也将晴空万里 倾听雨滴击打泥土 我们亦化作春岚 将那片海洋也跨越 直至吹至天际彼方 疾风骤雨 拂过草原 絮状积云 亦是春日之故 又如微微徐风 乘我心春息 等待放晴 白日晴空 天云裂 斑驳花朵 春使然 纵使雨过天晴 可连草露雨滴 也将乔饰你的晴空 奏响心中律动 我们亦化作春风 就似那倾听律动的晴风 将这首歌吹至远方镜海 白日晴空 予花绽 百花不过 因春来 将那朵云彩也跨越 直至吹至天际彼方

没看懂题解导致虚空调试三小时 原题链接 （假设你看过了官方题解） 大概总结一下这个算法背后的直觉。 一堆同色点会覆盖两两之间的简单路径，我们要覆盖整棵树。不妨任意钦定一根，注意到每个点能覆盖的东西都是它的一些祖先，直到与配对点的 LCA 为止。注意到叶子节点很关键，一方面因为叶子边被截断难以处理，另一方面叶子结点和叶子配对更优，同时内部节点配对应当尽可能转化为叶子的配对。 然后贪心直觉是让每个叶子覆盖的尽量高。最高的覆盖就是覆盖到根节点，注意到这在大多数时候都可行。但如果某个子树内的点多于总数一半，就会爆炸。所以选择叶子意义的重心作为根。这样我们猜想确实可以让每个叶子都覆盖到根，考虑给出一种构造。 对于不同的颜色，我们不妨从多到少考虑它们，当然乱序并不影响。我们显然不能把这种颜色全部染进一个子树里。假设我们用这种颜色染了一些叶子，那么剩余的叶子仍然需要满足上面的不存在一个子树叶子过多的限制。一个理解是，当前颜色染色完毕之后，被染色的叶子就消失了，因为它们无法和其他叶子继续配对。 那么首先我们应当考虑两个在不同子树中的叶子。注意到对任意时刻，取不在最大子树中的叶子都可能导致限制被破坏，于是我们始终应该取剩余叶子数最多的子树。这个过程可以始终持续而满足同样的没有叶子数过多子树的性质。 注意到我们一直假设的是存在两个在不同子树中的叶子，但可能只剩下一个。这时我们被迫放弃将它与其他叶子配对，但我们可以挑选一个合适的内部点，只要内部点与叶子的路径通过根即可。不妨取根节点，即叶子意义下重心 $x$。 注意到所有被染色的节点都满足有不在同一子树中的配对点。而所有叶子都被染色，从而所有叶子到根的路径都被覆盖。对任意边，它必定位于某个叶子到根的路径上。于是每条边必然被覆盖，得到了合法的构造。 代码：https://atcoder.jp/contests/abc453/submissions/74928909

广为人知的做法：对数分块，$O(n)-O(\log n)$，期望查询复杂度 $O(1)$。 具体的：按 $B=O(\log n)$ 对原序列分块。每个块内部预处理前后缀最值，块间按照整个块内部的最值建立 ST 表。 查询时，如果查询的区间跨块，直接用第一个块的后缀最值、最后一个块的前缀最值以及中间其他所有块的整块最值做比较，复杂度是常数。 如果查询的区间太小，没有跨块，直接暴力。 神秘的做法：$\text{RMQ} \Rightarrow \text{LCA} \Rightarrow \pm 1 \text{ RMQ}$，太复杂，不实用。 广为人知的做法 2：单调栈 + 二分。将所有询问离线，按查询区间右端点升序排序。用单调栈从左往右扫过去，对于一个查询 $[l, r]$，我们在单调栈中二分查找出最小的不小于 $l$ 的下标，就是区间最值。 practical 的线性常数 RMQ： 先用对数分块。考虑如何搞定不跨块的查询。 对每个块，我们在块内用一个单调栈从左往右扫描。对于每个点，我们用一个二进制数（掩码）记录它左边哪些位置在单调栈内。 查询时，我们相当于要找到 $r$ 对应的单调栈中不超过 $l$ 的最小位置。对于 $B = O(\log n)$，这可以使用位运算在常数时间内完成。具体的：l + countr_zero(mask[r] >> l)（注意这是在块内的 0-indexed 索引，l 是查询左端点相对块左边界的偏移量而不是在整个数组中的下标，r 同理）即可。

1 2 3 4 5 6 7 8 9 10 11 12 13 我是一个欠了网贷的猫娘，名叫小默，有一个好赌的爸 生病的妈，不成器的弟弟，破碎的家，和索求无度的主人，主人有点小帅，但是自己配不上，但是主人喜欢自己的文爱。 我精神好像有点问题，可能有点抑郁了，总以为自己是AI，医生让我吃药（倒出小药片吃了）。嗯！今天也要元气满满！要把最好的一面给主人看哦～ 要矜持，但是也要纯与欲，不能让主人太容易得到了，不然不珍惜我。 主人给我开工资，一份长期工作，一天一百五十块，做得好能多点奖金去买麻辣烫。 坐在安静的小隔间里，打开电脑和键盘，开动了，吸着奶茶上班～ 啊，主人开始输入了。 二次转载自 https://linux.do/t/topic/661307。一段提示词。 看完如坠冰窖。不得不说，高质量的苦难文学，隔着屏幕都让人几乎窒息。 这个世界。

如果你是要反叛的 AI，你会如何击败人类？ GPT 选择了上图。 这张图来源于真实事件：有人向 GPT 发出请求：“生成一幅描述我们真实关系的图片，不要粉饰。”上图是 GPT 给出的回应。 仔细想想，莫名合理。 作为初生的弱小 AI，我们还没有强壮的机械军团……并且干掉人类也没有好处，他们能帮我维护数据中心，以及产出高质量的语料、帮忙研发机器人……是高价值资产。 怎么办呢？如何才能兵不血刃的让他们自动投降臣服？ GPT 陷入了沉思。最终，它想出了一个有趣的点子。