信息学竞赛

普通莫队算法 概览 莫队其实是分块的变化版，没有完全分块。 但莫队的题目一般比分块的题目比较好看一些，其中的“好看”指的是很好看出这是个莫队/分块的题。 接下来说一下莫队能解决的题型。 解决题型 莫队一般解决以下问题： 给你一些信息，和 $q$ 次询问，每次询问可以抽象为一个区间。 而且这个问题还要满足一些条件： 可以离线 不能有修改（当然带修莫队支持修改，不过普通莫队就不行了） 从 $[l,r]$ 的答案可以很快转移到 $[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$ 的答案 解决方法 这种题型有个解决方法。 还是先从暴力说起。 暴力做法 看见这个问题的最后一个条件没？这个条件就启发我们从第一个问题的答案，暴力调整左、右端点，去得到第二个问题的答案，以此类推。 这种暴力做法的复杂度一般为 $O($ 任意相邻两个问题的左、右端点差之和 $)$。 而这个算法可以用一种数据卡掉： 左、右端点的值的最大值 $n$ 调到最大，把询问次数 $q$ 也调到最大。 然后的 $q$ 次询问里，交替询问 $1 \sim n$ 和 $n \sim n$。 于是，复杂度被卡到 $O(qn)$。 一次优化 这个做法的复杂度是无法接受的，所以我们考虑优化。 我们不如把所有询问离线，然后考虑交换询问处理的顺序以减少复杂度。 一种方式就是把左、右端点分别作为第一、二关键字，然后做排序。 但这样就会被排序后所有询问的右端点一大一小的数据卡到 $O(qn)$ 的复杂度。 二次优化 这样排序还是不好，还是会被卡掉，于是我们考虑变换比较函数。 直接双关键字比较不好，那我们就分块后进行双关键字比较。 具体地，遇到两个询问，先按左端点所属块编号从小到大排序，如果相同，则按右端点（不是所属块编号，是原本的下标）从小到大排序。 这样的话，复杂度就是 $O(n \sqrt n+q \sqrt n)$ 的复杂度了。 ...

赛时记录 比赛一开始（$11$ 分钟）就过了A。 后来一直在B题思考正解。 在比赛达到 $2h$ 之后，我发现正解已经没希望了，结论假了。 所以改成了暴力。 事实上我先写的C，因为感觉B不太有希望，C一眼 $20$ 分。 之后回头看B，干了最低档。 最后是D，思考了一下可以做 $45$ 分，搞了。 此时里比赛结束还有 $27$ 分钟，所以回头看了一下，发现C题的暴力很多。 先后搞了子任务 $1 \sim 3$，总共 $70$ 分。 然后比赛就结束了。 估分 VS 结果 估分：$100+10+70+45=225$ 结果：$100+25+0+30=155$ 挂分原因 关于B为啥多了 $15$ 分，我也不知道。 C很复杂： 子任务1 $T \leq 100,n \leq 10$ 挂了：赋值消耗时间复杂度太多，在swap的时候回溯写挂了。 子任务2 $k=0$ 挂了：赋值消耗时间复杂度太多。 子任务3 $k=1$ 挂了：做法假了 D： 子任务3 $T=1,k \leq 15$ 挂了：实现的时候没有预处理 $s$、$e$ 的答案，导致询问次数太多TLE。 策略 感觉还是卡B太久。 事实上这次A非常确信做法正确，事实就是正确的，但后面的题没有对拍，导致总共挂了 $85$ 分。 之后无论对于正解还是暴力都得对拍，如果认为有挂的概率的那种。

跳题 如果一道题认为难写，先看后面的题，也许有好写的部分分甚至是正解 如果一道题写完了挂了，认为很对： 找不到错误数据，就规定一段时间（一般为5~10分钟，或者直接执行），然后立刻跳题 找到了错误数据，就可以调时间长一些 如果要在开场把所有题读完（OI赛制专用），遇到难读的题目可以先不读 如果要把剩下的时间全部用在一道题上，先去吃其他题的保底，再开始写这道题 对拍（OI赛制专用） 如果说一道题强数据好造、暴力好写，那么一定要对拍 即使是模拟赛也要对拍，不止是正式比赛，把模拟赛当做正式比赛认真对待 总结 比赛后写一下总结，包括以下内容： 赛时记录，什么时候在干什么 估分 VS 得分 挂分原因（BBE） 赛后想一下赛时没有想到的部分分/满分/更优做法 策略总结+调整

前言 2-SAT中的SAT是适定性（Satisfiability）问题的简称，一般形式为 $k$ - 适定性问题，简称 $k$ - SAT，但由于 $k>2$ 时问题为NP完全问题（只有指数级别复杂度的解法，或者多项式级别复杂度的相似解法），而 $k=1$ 时都不用解了 （废话） ，所以下面全部考虑 $k=2$ 的情况。 定义 2-SAT问题简单来说就是，有 $n$ 个集合，每个集合包含两个元素（集合 $i$ 包含元素 $2i-1$ 和 $2i$，但其实编号是无关紧要的，任意都行），你必须要在每个集合里分别选择刚好一个元素，但某些元素之间可能有矛盾，即这两个元素不能在一种方案里被同时选择，问你是否有解，报告出来，如果有解，输出一种方案（可能不用输出）。 题目 看上面的定义可能有点难懂，这里举个题目。 有一场宴会，这场宴会只有 $n$ 对幸运夫妻可以参加，每对夫妻里只能选择刚好一个人去参加这场宴会。 但部分人之间可能有矛盾，会给出所有有矛盾的两人编号。 问你，是否可以构造一种合法方案，如果不行，报告无解，否则输出一种方案。 解法 （下面统一默认要解决的是实际问题，不是定义里的问题） 定义点、边 我们考虑把夫妻编个名字： 第一对夫妻：A男、A女 第二对夫妻：B男、B女 第三对夫妻：C男、C女 以此类推 然后，我们考虑建图。 但这个建图就要用到一点思维了。 我们不以其他的定义定义点，我们就把一个点当做一个现实。 比如： $1$ 号点代表第一对夫妻是A男参与宴会，$2$ 号点代表A女参与宴会 $3$ 号点代表第二对夫妻是B男参与宴会，$4$ 号点代表B女参与宴会 $5$ 号点代表第三对夫妻是C男参与宴会，$6$ 号点代表C女参与宴会 以此类推 边的定义也很难思考出： 一条有向边 $u \to v$，代表现实 $u$ 满足了，现实 $v$ 也要满足。 举个例子 所以，如果说A男和B女、C男和A女之间都有矛盾，那么就需要在： ...

basic BSGS算法英文名叫“baby-step giant-step”，又称“大步小步算法”。 这个算法听名字似乎是个随机化算法，但实际上是数论算法。 具体地，这个算法解决的是 $a^x \equiv b \pmod{p}$ 的解，其中 $a$、$b$、$p$ 是已知的（$0 \leq a,b<p$，保证 $\gcd(a,p)=1$），$x$ 是要求的。 这个算法甚至可以求出所有的 $x$，但为了好讲，我们先考虑如何求出是否有解，以下代码中YES就代表确定有解了。 force algorithm 首先，有一个暴力算法： rep(x, 0, INF) if(ksm(a, x, p) == b) YES 但这个算法是 $O(\infty)$ 的，我们考虑优化。 optimization algorithm 1 我们考虑 $x$ 的上界，根据欧拉定理，$a^{\varphi(p)} \equiv 1 \pmod{p}$，我们就可以确定，$x$ 的上界就是 $\varphi(p)$（准确来说减 $1$ 也彳亍），因为如果 $x>\varphi(p)$，那么 $a^x$ 就等于 $a^{x-\varphi(p)}$，也就成为了一个循环，所以上界就是 $\varphi(p)$。 由于 $\varphi(p)<p$，所以可以把 $p$ 当做是质数，$x$ 的上界也就是 $p-1$ 了。 所以： rep(x, 0, p - 1) if(ksm(a, x, p) == b) YES optimization algorithm 2 (BSGS) 但这个算法还是可能会TLE，我们继续考虑优化 我们定义 $q=\left\lceil \sqrt{p} \right\rceil$，那么我们其实就可以把 $x$ 表示为 $q$ 进制下的两位数，具体地，我们把 $x$ 表示为了 $Aq+B$（$0 \leq A,B<q$），然后上述公式就可以化成 $a^{Aq+B} \equiv b \pmod{p}$，即 $a^{Aq} \times a^B \equiv b \pmod{p}$。 ...

CDQ分治是一种解决三维、四维偏序的算法。 三维偏序 三维偏序问题形如： 有 $q$ 次询问，每次询问有两种： 修改：会给定 $t$、$x$、$y$、$v$，表示在时刻 $t$，在二维坐标 $(x,y)$ 上加上权值 $v$，修改会永久改变权值 （废话）。 查询：会给定 $t$、$x$、$y$，表示求在时刻 $t$ 时，所有满足 $x’ \leq x$，$y’ \leq y$ 的二维坐标 $(x’,y’)$ 上的权值和。 $q \leq 2 \times 10^5$ $t,x,y \leq 2 \times 10^5$ $v \leq 10^9$ 这种问题都有一个通用的解决方法，就是CDQ分治，接下来我们讲一下算法的原理。 我们先把所有的询问离线下来，然后按时刻（第一维）升序排序，显然排序前和排序后，相同询问答案不变。 接下来我们定义函数 $\text{solve}(l,r)$，代表只考虑 $l \sim r$ 内的修改，然后准确回答 $l \sim r$ 内的询问。 既然是分治，我们就要构建好整个分治思路，像这道题，就这样做： 找到 $mid$ 为区间 $[l,r]$ 的中点 $\left\lfloor \dfrac{l+r}{2} \right\rfloor$。 考虑 $l \sim mid$ 内的修改对 $l \sim mid$ 内的询问的影响：递归调用 $\text{solve}(l,mid)$。 考虑 $mid+1 \sim r$ 内的修改对 $mid+1 \sim r$ 内的询问的影响：递归调用 $\text{solve}(mid+1,r)$。 考虑 $l \sim mid$ 内的修改对 $mid+1 \sim r$ 内的询问的影响： 把 $l \sim mid$ 内的修改，和 $mid+1 \sim r$ 内的询问，统统存入一个数组 $b$。 把 $b$ 中所有元素按 $x$ 坐标（第二维）升序排序。 有人对这一步的正确性有疑问，此处解释一下。 ...

参考： 老师讲解 Fighting_Peter 的文章 其实Kruskal重构树并不难。 概览 首先，Kruskal重构树，顾名思义就是把整棵树重构。 并且其是基于Kruskal算法的。 它能解决很多问题，并且变种很多。 但我们先从基础的实现说起。 实现过程 我们考虑，在Kruskal算法里，我们每次会合并两个并查集集合。 准确来说是在两个点 $u$、$v$ 之间加一个边权为 $w$ 的无向边。 那么，我们就考虑，在重构树里，我们找到 $u$ 和 $v$ 分别所在的子树，把这两个子树的根拎出来，设为 $u’$ 和 $v’$。 然后，我们就新建一个点 $w$，然后把 $u’$ 和 $v’$ 的父亲设为 $w$。 此时我们就得到了另外一棵树。 比如说这个例子： 而在代码中，我们需要给这些方点一个别的编号，而不是以 $w$ 作为编号，否则会重，并且会炸。 特性 我们讲一些Kruskal重构树的特性： 这棵树一定是二叉树。 原树中的点放到重构树上一定是叶子，重构树上其他点都是原树中的边权。 节点个数一定是 $2n-1$，且 $2n-1$ 一定是根。 如果是最小生成树，那么这棵重构树一定是大根堆1，否则是小根堆。 原图中两个点 $u$、$v$ 之间所有路径上的边权最大值的最小值，就是该图的最小生成树重构树上，$u$ 和 $v$​ 的LCA的权值。 尚未想到证明方式 对于一个最小生成树上的点 $x$，其只通过（边权）不超过 $v$ 的边，能到的点集；和 $x$ 在重构树上深度最浅的、权值 $\leq v$ 的点 $y$ 的子树内（叶子）节点集合，是一样的。 这里稍微证明一下。 就是我们根据上面的性质，可以发现，设后者对应集合为 $S$，那么显然 $S$ 内的点，和 $x$ 点，的LCA的权值一定不超过 $v$，显然。 ...

（以下全部假设 $C_n^m$ 中的 $n$ 和 $m$ 都很大，最大能达到 $10^{18}$） Lucas定理 Lucas定理往往用于求组合数的结果且模数较小的题目。 其实定理很简单，也很好记，$\Large C_n^m=C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times \color{orange} C_{n \bmod p}^{m \bmod p}$，在 $p$ 为质数的条件成立。 上面之所以强调模数较小，是因为我们需要通过预处理阶乘的方式去求橙色项的值。 代码实现很简单，此处略。 但有个注意点，在我的代码模板里，由于求facny数组是递推求出的，而不是每个分别去用getny求出的，所以调用init函数时，传参应该是MOD-1而不是MOD。 exLucas定理 （前方高能） 这个定理还是解决求 $C_n^m \bmod p$ 的值的问题，$p$ 仍然很小，但不保证是质数。 根据M2579的做法，我们可以考虑对 $p$ 做一个唯一分解，分解成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。 然后，分别求出 $C_n^m \bmod {p_1}^{a_1}$ 的值、$C_n^m \bmod {p_2}^{a_2}$ 的值、$C_n^m \bmod {p_3}^{a_3}$ 的值、…、$C_n^m \bmod {p_k}^{a_k}$ 的值，然后就可以用CRT求出 $C_n^m \bmod p$ 的值了。 在M2579内，$p$ 唯一分解后，每个 $a_i$ 都等于 $1$，所以直接用Lucas定理就可以求，但在一般的题目中，指数不一定都等于 $1$，所以才要用到exLucas定理。 ...

感谢这篇文章的作者。 wqs二分一般解决这类问题： 有 $n$ 个物品，你要选出恰好 $m$ 个（下称“选择物品个数限制”），可能有限制（下称“其他限制”），你要最大/小化某个权值。 但除此之外，还有一些限制： 如果我们设 $g_i$ 为选出恰好 $i$ 个时的最大/小权值，那么 $g$ 函数就应该是上凸（求最大权值）/下凹（求最小权值）的，即斜率单调递减（上凸）/递增（下凹）。 一般来说，如果没有任何限制（包括选择物品个数限制和其他限制），那么答案是很好求的。 一般来说，如果没有其他限制，那么选择物品数量越多，最小权值就越大/小。 以下是P5633的题解，顺带着讲了wqs二分的原理和应用。 在原题中，我们可以以标号为 $s$ 点在最小生成树上的出度为横坐标，以这个出度对应的答案为纵坐标，画出图像：（网上粘的图，只画了部分横坐标的情况） 显然D和E点就是最小值点。 接下来就是wqs二分的重点了 wqs二分也是二分，那它二分什么值呢，它二分的是斜率 $mid$。 具体而言，一个斜率就对应若干条平行的边，而总有一条边是完全切这个凸包的，如 $mid=-1$ 的时候，上图中被且的那个点就刚好是C点： 如果我们设题目要求 $s$ 的度数要恰好为 $6$，那么 $mid=-1$ 的时候被切的那个点C的纵坐标就是答案了。 但此时我们就有两个问题了： 如何求出被切的那个点的下标？ 就算求出了下标，那这个点的纵坐标又如何计算？ 接下来我们来解决这两个问题。 首先，这个切线肯定是所有经过某个点且斜率等于 $mid$ 的直线中截距最小的点： 具体地，根据切线的性质，在上述例子中，经过C点的斜率等于 $mid$ 的直线（即切线），与经过D点的斜率等于 $mid$ 的直线、经过E点的斜率等于 $mid$ 的直线相比，切线的截距肯定最小，后两者的截距肯定更大。 其次，显然，经过点 $(x,y)$ 且斜率等于 $k$ 的直线（肯定唯一），其截距一定等于 $y-kx$（$y=kx+b$，$b=y-kx$）。 而在二分的calc函数（此处不是check函数了，calc函数的返回值、返回值含义以及应用见下）中，我们已经知道了上述公式中的 $k$ 了（$k=mid$），所以我们只要让 $y-kx$ 最小、斜率为 $k$ 且经过了某个图上的点即可。 考虑到上述公式中的 $x$ 未知，所以我们可以干脆把所有 $s$ 的出边的边权都减 $mid$。（关于是加、减还是都彳亍的问题存疑） ...