> 这篇文章将提出 回文树 的概念，一种解决回文串相关问题的优美数据结构。 感谢它的发明者 Mikhail Rubinchik [http://codeforces.ru/profile/MikhailRubinchik]，在 Petrozavodsk Summer Camp 2014 中向我们讲述了这一概念，使得这篇文章的创作成为可能。 结构 和其他所有树形结构一样，回文树由节点构成。在这里，每个节点代表了一个回文串。 四节点回文树的样例在节点之间有边相连。一条从 $u$ 连至 $v$ 的树边上会标有一个字母 $x$，表示在 $u$ 处的回文串左右加上一个 $x$ 得到 $v$ 处的回文串。 ‘aba’ 由 ‘b’ 在左右两边各添加一个 ‘a’ 得来同时也存在着一些非树边，我们称之为 $fail$ 指针。从 $u$ 指向…
Description [https://atcoder.jp/contests/agc002/tasks/agc002_f] 把一共 $n$ 种颜色，每种颜色 $k$ 个的球排成一行，然后把每种颜色的第一个球涂成白色。求最终颜色序列的种数。 Idea 我们可以看成 $n+1$ 个颜色，其中白球有 $n$ 个，剩下每种颜色 $k-1$ 个。题目的限制条件为，颜色序列的每个前缀中，白球数量不得小于其他球的数量。我们可以利用这个性质从后往前 $DP$。 设 $f_{i,j}$ 表示放下 $i$ 个白球，$j$ 种其他颜色球的方案数。 * 新增一个白球，直接由 $f_{i-1,j}$ 转移过来； * 新增一种其他的颜色，也就是加入了…
定义 当我们提到 “Treap” 的时候，我们实际上说的是 “Tree” + “Heap”。Treap 的每个节点拥有两个值：”Key” 和 “Val”。其中 “Key” 满足堆的性质，而 “Val” 满足二叉搜索树的性质。 朴素的 Treap 在插入的时候给每个点一个随机的 Key，通过旋转来满足堆的性质。对于 FHQTreap，我们不再使用旋转维护，转而使用拆分和合并。 核心操作 拆分 我们将一个 Treap 按特定的值 Val 拆分成两个 Treap – 左树和右树，使得左树的所有值小于等于 Val，而右树的所有值大于 Val。 void split(int now,int &a,int &b,int val)…
Description [https://www.luogu.org/problemnew/show/P2501] 现在我们有一个长度为 n 的整数序列 A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。 求最少的改变数量，和在改变的数最少的情况下，每个数改变的绝对值之和的最小值。 Idea 首先一个套路。 要求严格单调的序列，就先将 $a_i-i$，对处理后的数列 $a’$ 做 $LIS$ 即可。 对于第二问，我们可以区间 $DP$。 枚举 $LIS$ 保留的相邻两个数 $i,j$，它们之间的数一定是前一半和 $a’_i$ 相等，后一半和 $a’_j$ 相等。因为数列随机生成，转移的数量远远到达不了 $\Theta(n^…
自中国在联合国投下反对票和台湾公投受挫已经过去了一个多月。 这一个多月，包括我在内的无数 LBGT+ 运动支持者、参与者，或是组织者，都在思考一个问题：我们的运动是否陷入了一个尴尬的困境？而未来又将向哪个方向发展？或许我们应该后退一步，审视这条我们从一开始选择的道路。 我们所追求的 心理学家亚伯拉罕·马斯洛 1943 年在《人类激励理论》论文中所提出，人类需求像阶梯一样从低到高按层次分为五种，分别是：生理需求、安全需求、社交需求、尊重需求和自我实现需求。 事实上，自 1992 年公安部明确表态同性恋合法，1997 年新刑法中删除 “流氓罪” 后，生活在中国大陆的 LGBT+ 群体的生理需求已经得到了保障。在 2018 年 11 月 6 日于日内瓦召开的中国 UPR 第三轮审议上，中华人民共和国代表团首次正面回答了有关于中华人民共和国 LGBT+ 权益的相关问题： > 1、我国一贯尊重…
Description [https://loj.ac/problem/2116] 风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。 很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n 个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 $x_i$。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u 为编号），然后在 u 开一家面向年龄在…
Description [https://www.luogu.org/problemnew/show/P5048] 给你一个长为 n 的序列 a，m 次询问，每次查询一个区间的众数的出现次数，强制在线。 Idea 分块。 预处理每两块之间的众数出现次数；用 $vector$ 存每种数值对应的所有元素下标；记录每个元素在 $vector$ 里的位置。 询问时，整块之间的答案已经预处理出来了，考虑 $2\sqrt n$ 个边角元素。 对于左边的边角元素 x，我们在相应的 vector 里找到下标为 $p_x+ans$ 的元素y，若 $y\leqslant r$，则说明该数值在范围内有至少 $ans+1$ 个数，暴力更新答案即可。…
Description [https://www.luogu.org/problemnew/show/P4169] 需要维护一个结构，要求支持以下2个操作。 1. 向二位空间内插入一个点。 2. 给出一个二维点，询问距离这个点曼哈顿距离最近的点的曼哈顿距离。 $n, m ≤ 3 × 10^5 , T = 3s$ Idea 本题可以使用 kd-tree 加上替罪羊树做到按题意模拟，但是我还不太会。 所以我们用 CDQ 分治解决这个问题。 对于每个要查询的点，二维空间被它分割成四个象限，我们只考虑第三象限的做法，然后不断翻转即可。 这样我们去掉了曼哈顿距离中的绝对值，将题目转化为一个简单的三维偏序问题： 对于一个询问 $(x, y)$，找到满足时间戳在其前且 $x_i \le x, y_i \le y$ 的点中 $x_…