注意到\(\sum\limits_{i=2}^N|x_{p_i}x_{p_{i-1}}|+|y_{p_i}y_{p_{i-1}}|\)。本质上是两个点之间的曼哈顿距离。 而曼哈顿最小距离生成树要\(O(n^2\logn)\)，显然过不了。 注意到我们写过一个叫莫队的东西。 而莫队的复杂度为\(O(n\sqrtn)\)，也就是我们要求的东西。 加一点小优化，奇偶排序。 就可以过了。 怎么证明？ 可以看一看这一篇博客 精简来说就是控制了左右指针跨越块的数量。 include<bits/stdc.h> usingnamespacestd; constintmaxn=1000001; st...

提供一种需要卡常的分块写法。 首先看到\(\operatorname{popcount}\)操作，便可以自然而然的想到在值域上做文章。 首先因为\(\operatorname{popcount}\leq\logx\)。 所以可以想到对于一个序列来说，进行一次\(\operatorname{popcount}\)操作后至多有\(\logV\)个不同的数字。 并且在对这个区间进行全局操作时不同数的数量不增。 因此考虑分块。 块内最开始用\(tag\)记录加法操作。 对于块内如果有整块\(\operatorname{popcount}\)操作则转换成记录每个值都变成了什么。 由于所有值不大于\(\l...

首先大力推式子。 为了方便，先假设\(2\leqz\)。 \(x\frac{y}{z}=n\) \(\frac{x-y}{z}=(n-1)!\) 很显然的\(z|x\)以及\(z|y\) 令\(m=\frac{x}{z}\)以及\(k=\frac{y}{z}\) 得到\(\frac{m\timeszk}{mk}=n\) \((m\timeszk)=n\times(mk)\) \((mk)+(z1)\timesm=n\times(mk)\) \((z1)\timesm=(n1)\times(mk)\) \((z1)|(n1)\times(mk)\) \((z1)|(n1)\times(mk)\t...

动态开点线段树 使用场景 \(4\timesn\)开不下。 值域需要平移（有负数）。 什么时候开点 显然，访问的节点不存在时（只会在修改递归时开点）。 trick 区间里面有负数时，\(mid=(l+R1)/2\)。 防止越界。 例如区间\([-1,0]\)。 开点上限 考虑到update一次最多开\(\logV\)个点（最多递归\(\logV\)次）。所以总空间应当开\(O(m\logn)\)。 代码 include<bits/stdc.h> defineintlonglong usingnamespacestd; inttot; intn,q; constintmaxn=4...

前言 斜率优化是一种经典的单调队列优化类型，虽然它的名字很高大上，但是其思想内核非常简单，这篇博客就是用来帮助各位快速入门的 提示：本博客以单调队列的思想理解斜率优化 引入 dp优化可以怎么分类？ 数据结构维护决策点集的插入与查找 算法维护决策点集大小，取出无用决策点 而斜率优化dp属于第二者，且常常用于优化序列分割问题 Q1 P3195 A1 先列出一个朴素的dp方程: \(dp_i=min(dp_j+(pre[i]+i-pre[j]-j-L-1)^2)\) 然后我们考虑决策点\(j,k\)满足\(k<j\)且\(j\)优于\(k\) 那么有： \(dp_j+(pre[i]+i-L...

前言 合并操作一直是OI中一大考点，今天请各位跟着笔者来梳理一下各种合并操作。 启发式合并 几乎可以说是最经典的合并了。 假定我们可以在\(O(k)\)的时间内往某个集合中插入一个数，那么我们就可以在\(O(n\lognk)\)的时间内合并若干个元素总量为\(n\)的集合。 集合启发式合并 [NOI2022]众数 看到查询绝对众数我们便想到一个方法： 用桶记录每个元素出现次数，查询时从序列中随机抽取\(\logq\)个数验证是否是绝对众数。 易证这种做法期望是正确的。这里略去。 然后对于在末尾插入删除以及拼接多个序列，我们可以用双端队列维护。 但是在拼接序列是怎么插入元素，暴力插入元素是\(O...

首先考虑怎么暴力。 考虑把每个数进行\(B\)进制分解，然后我们惊奇的发现这两个操作就是把最低位去掉和往最低位后面插入一个数。 然后我们顺藤摸瓜，把每个数的分解扔到Trie树上，我们发现我们要找到一个节点，使得所有单词节点到其的距离之和最短，答案就是这个最短距离。 这里直接考虑一个Trie树上dp，记所有单词节点到节点\(i\)的最短距离为\(dp_i\)，然后直接去转移。 然后考虑找找性质。 记\(sz_i\)表示以节点\(i\)为根的子树内单词节点数量，我们发现节点\(i\)的转移如下\(dp_i=dp_{fa_i}sz_j+(sz_1sz_j)\)。 又因为\(sz_i\leqsz_{f...