主页
搜索
最近更新
数据统计
赞助我们
申请密钥
系统公告
1
/
1
请查看完所有公告
2025.4 做题记录
最后更新于 2025-04-29 10:39:44
作者
huangjinxiu
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
### [T377858 序列维护](https://www.luogu.com.cn/problem/T377858) lxl 讲课题单中的题。 注意到 $\sum k $ 的值是有保障的，所以考虑 [P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048) 的思路，每次找到当前最优贡献二元组后强制其无法再产生贡献，然后继续找最优贡献。 因为区间询问，区间长度之和是没有保障的，所以不能像 超级钢琴 一样对区间的每个左端点维护其右端点范围做 rmq。 考虑把贡献转化为这样的形式 ：$i$ 在 $[L_1,R_1]$ 中选取，$j$ 在 $[L_2,R_2]$ 中选取，满足 $i \le j$ 且使得 $a_i-a_j$ 最大的 $(i,j)$ 。 这样做的好处是可以很方便得拆除贡献后 $split$ 。 考虑将贡献形式 $[L_1,R_1]$，$[L_2,R_2]$ 看成二维平面上的一个矩形，加入 $i \le j$ 的限制后即只能选取直线 $y=x$ 及其上方的点。每次找到当前最优决策点 $(i,j)$ 后显然可以把矩形分裂成四个小矩形 ： - $[L_1,i-1]~,~[L_2,j]$ - $[i,R_1]~,~[L_2,j-1]$ - $[i+1,R_1]~,~[j,R_2]$ - $[L_1,i]~,~[j+1,R_2]$ 每次开一个结构体存储矩形，在生成一个矩形的时候计算出其最优贡献，这个用线段树是好做的： 将贡献分为两类: - 一类是 $[L_1,R_1]$ 与 $[L_2,R_2]$ 中相交的部分，这部分的答案线段树合并信息时用 $lc$ 的最大值与 $rc$ 的最小值相匹配，以及 $lc$ 与 $rc$ 本身的贡献更新即可。 - 另外一类更好做，不相交直接左侧取最大值，右侧取最小即可。 - 然后按 $[L_1,R_1]~,~[L_2,R_2]$ 的关系分讨即可。 - 需要注意不能出现 $i > j$ 的情况。 - 同时还要维护 $(i,j)$ 的位置方便后续继续分裂贡献。 - 区间加修改更是无比容易，打个 ```tag``` 就行了。 ### [AT_arc126_e [ARC126E] Infinite Operations](https://www.luogu.com.cn/problem/AT_arc126_e) 今天联考 T1 搬了不带修的弱化版做签到题，还是比较简单的。 因为操作可以进行无限次，所以这实际上是个在值域上做传递使得最后每个数都变成平均数的过程。 考虑当 $x<y<z$ 时，我们无论如何也不会将 $z$ 的值直接传给 $x$ 。因为这样相比于 $z$ 传到 $y$ 再从 $y$ 传到 $x$ 会少一次贡献。 所以传递一定是发生在一条按值域从大到小的传递链上。 考虑计算答案。设计函数 $f(n,x,y)$ 表示前 $n$ 个数中已经全部变为平均值 $x$ ,且第 $n+1$ 个位置上的值为 $y$ ，再将前 $n+1$ 个数全部变为平均值，也就是$\frac{nx+y}{n+1}$ 后给答案带来的贡献（以下统一乘了 $2$，问就是联考要求输出两倍）。 - 显然有 $f(1,x,y)=y-x$ - 打表猜测 $f(n,x,y)=n\times(y-x)$，以下为证明。 - 考虑从 $y$ 传一个 $\Delta$ 到其相邻的 $x_1$ 中，然后 $x_1$ 再传递到剩下的 $x$ 中使得所有 $x\gets x+\frac{\Delta}{n}$ ，而 $y\gets y-\Delta$。 - 这一阶段的操作完成后对答案的贡献为 $2\times \Delta +f(n-1,x,x+\Delta)$ 。 - 考虑 $\Delta$ 取值的上界，显然当 $y-x=0$ 时无法继续发生值的传递。而操作一次之后 $y-x$ 会缩小 $\frac{(n+1)\Delta}{n}$ 。所以 $\Delta$ 取值的上界为 $\frac{n(y-x)}{n+1}$ 。 - 带入得对答案的贡献为 $2\times\frac{n(y-x)}{n+1}+f(n-1,x,x+\frac{n(y-x)}{n+1})$ 。 - 显然若 $f(n-1,x,y)=(n-1)(y-x)$，则可推出 $f(n,x,y)=n(x-y)$ 。而 $f(1,x,y)=1\times(y-x)$ ，故 $f(2,x,y)$ 也满足。则 $f(n,x,y)=n(y-x)$ 。 证明了这个结论后剩下的就好做麻了，联考T1 直接排个序扫一遍就完了。而原题带修则考虑推一下增删一个数的贡献，然后发现可以用值域线段树简单维护，就做完了（注意取模，以及最后答案除以 $2$）。 ### [P11355 [eJOI 2023] Teleporters](https://www.luogu.com.cn/problem/P11355) 3.27 定时训练 T1，拖到现在才写。\bx tybbs \bx k1lomiles 才知道线段树区间查 $\gcd$ 的复杂度是单 $\log$ 。 $Step ~1$ 观察变化的性质： - 记二人坐标为 $x_1$，$x_2$，选择的传送站坐标为 $c_1$，$c_2$。 - 则变化完成之后有 $x_1\gets 2c_2-x_1$ ，$x_2 \gets 2c_2-x_2$。 - 观察相对位置的变化，从 $\left\vert x_1-x_2\right\vert$ 变成了 $\left\vert 2(c_1-c_2)-(x_1-x_2)\right\vert$ 。 - 这个时候可以大胆猜测（本蒟蒻永远不会系列）答案是只与相对位置有关，与绝对位置无关的。而走到同一个位置则等价于相对位置为 $0$ 。 - 所以我们只需要用若干 $2$ 倍 $c$ 的差凑出 $x_1-x_2$ 就行了。 $Step ~2$ 继续推导： - 考虑将传送站按照 $f$ 进行排序。 - 我们发现若选取非相邻的两个传送阵一定可以转化为只选取相邻的两个传送阵以此达到等价的效果。例如选取 $c_1,c_3$ ，则可以先选取 $c_1,c_2$ ，再选取 $c_2,c_3$ ，效果是相同的。 - 而题目要求最小化每次选取的传送站的 $f$ 值的最大值。所以我们每次肯定要选按 $f$ 排序后相邻的两个。 - 如何判断能否凑出答案？等价给你一堆数（每个数可以多次使用），你使用加减运算符将其凑成 $x_1-x_2$ 。等价于给一堆数定系数使得这些数乘以系数的和为一个值 $k$。用裴蜀定理可以说明有解的充要条件是这些数的 $\gcd$ 整除 $k$ 。 - 判断有无解只用判断对应区间的 $\gcd$ 是否为 $x_1-x_2$ 的因数即可。 $Step ~3$ 整理思路： - 题目关于 $f$ 的限制 $[L,R]$ 该如何处理？ - 此时有两种思路。 - 思路一：全局查询是简单的，将按 $f$ 排序后相邻的 $c$ 的差 $k_i=\left\vert c_i-c_{i+1} \right\vert$ 按 $f_{i+1}-f_i$ 排序，每次二分前缀 $\gcd$ 判断即可。将全局查变为区间查，直接套一个莫队即可。复杂度 $O(n \sqrt{n}(\log n+\log V) \log+m(\log n+\log V))$。k1lomiles 写了但是被卡常了。 - 思路二：整体二分，还是按照 $f$ 排序，相当于 $k$ 的激活顺序按照对应的 $f$ 之差从小到大的顺序。这个整体二分离散化之后可做到 $O(n\log^2 n)$(好久没写整体二分了，要注意 ```solve``` 与撤销的顺序)。 - 延续思路二，有在线做法。参照 [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839)，做值域扫描线维护一颗主席树，每次二分在对应的根上区间查即可。这种写法好写好调，但是常数略大，且空间复杂度$O(n\log n)$。 题外话，说明区间查 $\gcd$ 的复杂度单次是 $\log n+\log_{\frac{\sqrt{5}+1}{2}} V$ 的：$\gcd$ 是有均摊复杂度的，有效的辗转相除次数不超过 $\log_\frac{\sqrt{5}+1}{2} V$ 。 ### [P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2)](https://www.luogu.com.cn/problem/P7561) 求前 $k$ 小曼哈顿距离。 先胡一个 lxl 上课说的单 $\log$： - 按超级钢琴的思路，每次维护每个点离其最近的点，每选择一个点对 $(a,b)$ 后将对应点 $a$ 中删去 $b$ 的贡献，对应点 $b$ 中删去 $a$ 的贡献，然后继续寻找 $a，b$ 的最优贡献，然后继续找全局的最优贡献。 - 考虑如何维护这个过程，因为曼哈顿距离有 $4$ 种情况所以直接按每个点的 $4$ 个象限分讨（这一步出来就有大粪的潜质了）。 - 对于每一个象限,都进行一次扫描线，建出对应的主席树。比如第二象限就是从左往右扫维护 $y_b-x_b$。每扫到一个点就将这个点对应的主席树版本设为当前版本。 - 每次对于一个点 $a$ 删掉 $b$ 的贡献在对应象限的主席树新建一个版本即可（注意共线的情况）。 然后是题解区的比较好写的做法： - 首先有个小 trick，曼哈顿距离 $\left\vert x_1-x_2\right\vert +\left\vert y_1-y_2\right\vert$ 与切比雪夫距离 $\max(\left\vert x_1-x_2 \right\vert,\left\vert y_1-y_2 \right\vert)$ 的互相转化。 - 通过将原图中的点映射为新点即可： - 曼哈顿距离转切比雪夫距离：$(x,y)\to(x+y,x-y)$。 - 切比雪夫距离转曼哈顿距离：$(x,y)\to(\frac{x+y}{2},\frac{x-y}{2})$。 - 这个证明手推一下就行了，是简单的。 所以这个题考虑将曼哈顿距离转化为切比雪夫距离，然后考虑二分答案求第 $k$ 小的点对距离 $d$，单次 ```check``` 只用判断是否存在 $\ge k$ 个点对的距离 $\le d$。 考虑如何 ```check``` 。我们先将点按照 $y$ 排序，然后每次 ```check``` 时只钦定每个点和在其前面的点产生贡献。每次从 $1$ 到 $n$ 枚举点，双指针维护合法的$y$。用 ```multiset``` 解决 $x$ 这一维的限制。具体的，每次双指针移动时加入当前点，去除 $y$ 不合法的点。每次可以 ```lower_bound``` 得到第一个满足 $x_j\ge x_i-d$ 的点，然后每次迭代器自增，判断是否合法。一旦合法的个数 $\ge k$ 就 ```return 1;```。 这样单次```check```是 $O(n\log n)$ 的，总复杂度 $O(n\log^2 n)$ 。 ### 小细节： - 二分的时候 $r$ 要设为 $4e9$，而不是 $2e9$。因为转成了切比雪夫距离极差翻倍了。 - 求点两点 ```dis```的函数不要写成求曼哈顿距离的了（好唐啊）。 - 最后求答案时可以求出所有距离 $< d$ 的点对，最后少几个就补几个 $d$ 。这样可以防止距离为 $d$ 的点对过多的情况。 ### [P6011 [SCOI2006] 动态最值](https://www.luogu.com.cn/problem/P6011) 简单题。用值域线段树维护下标，查询真正下标时相当于全局第 $k$ 小。删除一个点相当于把值置为 $0$。然后在维护最大最小值的线段树上毙掉这个点的贡献。 ### [P3287 [SCOI2014] 方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287) 二维树状数组模板题。 首先考虑一定是对于一段后缀进行加操作。 所以只用考虑起始点就可以刻画一次操作。 然后设计 $dp[i][j]$ 表示一共在 $[1,i]$ 中进行了 $k$ 次操作后 $[1,i]$ 且强制留下点 $i$ 的最长不降子序列长度。 显然有转移 $dp[i][j]=\max \limits_{1\le p<i \land 0\le q\le j \land a_p+q\le a_i+j-q} dp[p][q]+1$ 直接转移，枚举 $i,j,p,q$ 可以得到 $O(n^2 k^2)$ 的复杂度。 考虑用数据结构优化。从小到大枚举 $i$ 即可解决 $1\le p<i$ 的限制。 对于求 $\max \limits_{ 0\le q\le j \land a_p+q\le a_i+j-q} dp[p][q]$，这可以看作是在二维平面的一个前缀矩形求最大值。 使用二维树状数组可以简单维护。 参考普通树状数组，二维树状数组上的一个节点 $[x,y]$ 维护的是以 $(x-lowbit(x),y-lowbit(y))$ 和 $(x,y)$ 为顶点的矩形的信息。转移与查询时每次分两个维度枚举即可。 因为树状数组的特性，下标为 $0$ 是无法使用的，此题直接将可能为 $0$ 的 $q$ 这一维整体向右偏移一位即可。还要注意转移时是“滚动数组”，所以要先枚举 $q$ 更大的先转移。 ### [P3285 [SCOI2014] 方伯伯的OJ](https://www.luogu.com.cn/problem/P3285) 简单题。考虑用动态开点值域线段树维护。记录每个编号对应在线段树上的叶子节点位置即可。每次挪动相当于移动到最小/大的值的位置的 $-1$/ $+1$ 位置。这个预先把初始的值偏移，再把值域开大即可简单实现。至于初始的值可以预先打 $tag$ 处理。注意正确维护编号与节点的映射关系。 ### [20250403 T1](http://i.oj7.top/problem/1488) ~~大家都场切了~~。 问题可简单转化为一个长度为 $k$ 序列 $a_1,a_2,a_3,\dots a_k$，满足 $\sum_{i=1}^{k}=n(n<1e6)$。然后给每个 $a_i$ 配一个系数 $p_i=+1/-1$，使得 $\left\vert\sum_{i=1}^{k} p_ia_i\right\vert$ 最小。 ~~发现目前的贪心算法都是假的。~~ 考虑背包，问题变为可行性背包判定问题。容易直接用 $bitset$ 优化到 $O(\frac{nk}{\omega})$ 的复杂度。 然后有以下两种方式优化： 第一种，二进制拆分，复杂度 $O(\frac{n\sqrt{n}}{\omega})$ （不带 $\log$哦） 考虑经典自然根号结论，因为 $\sum_{i=1}^{k}a_i =n$，所以 $a_i$ 的种类数一定是小于 $\sqrt n$ 级别的。对于相同的值用多重背包的优化思路二进制拆分即可。 第一反应因为二进制分组复杂度可能带 $\log$ 。实际上是不带的，以下为说明： 考虑所有贡献了 $2^j \times a_i$ 的项的和。贡献的在 $bitset $ 上的操作数的和为 $\sum \min(\lfloor \frac{cnt_{a_i}}{2^j} \rfloor,1)$ ,显然 $\sum \frac{ cnt_{a_i}}{2^j}$ （有贡献的 $a_i$）$\le \sqrt{\frac{n}{2^j}}$ 。 假设每种 $a_i$ 都取到最大贡献，有总的 $bitset$ 操作次数为 $\sum_{j=0}^{\infty} \sqrt{\frac{n}{2^j}}$ 。注意到这是公差为 $\frac{\sqrt 2}{2}$ 的等比数列求和。于是总和为 $(2+\sqrt{2})\sqrt{n}$。所以复杂度乘的不是 $\log$ ,而是一个小常数。 第二种，线段树维护哈希，每次 或左移操作 二分 $LCP$ 均摊复杂度 $O((n+k)\log^2 n)$ 首先对于当前线段树维护的 $01$ 序列与左移 $k$ 位后 的 $LCP$ 可以每次二分哈希 $\log ^2 n$ 求出（别想着在线段树上二分，每次左移后线段树结构无法对应起来）。 然后判断 $LCP$ 后一位（如果没有就直接结束），如果是 $0$ 对 $1$ 直接赋值就行了。 接下来说明每次二分得到的 $1$ 对 $0$ 一定能找到与此对应的 $0$ 对 $1$，以此保障均摊复杂度的正确。 |-0111101001| |:-:| |**0111101001-**| 考虑上图的 $1001011110$ 或上其本身左移 $1$ 位的结果。 以下称位置 $i$ 为第一行从右到左的第 $i$ 个位置。 - 第一次二分显然会找到位置 $2$，然后 $0\gets 1$。 - 第二次二分会找到位置 $4$，此时不进行任何操作。 - 第三次二分会找到位置 $5$，$0\gets 1$，显然这次操作与第二次 “无效”的二分是可对应的。 - 第四次是位置 $6$。无操作。 - 第五次二分是位置 $10$，显然对应第 $4$ 此二分。 这样就可以说明，若当前的二分到的位置“无效”，则下一次二分到的位置一定有效果。 所以这样均摊复杂度 $O((n+k)\log^2 n)$。 ### [AT_arc150_f [ARC150F] Constant Sum Subsequence](https://www.luogu.com.cn/problem/AT_arc150_f) 联考 T3 大概理解一下题目在干什么，可以发现令 $F_i$ 表示前缀的子序列包含所有和为 $i$ 的序列的最靠前的位置。 容易发现有转移 $F_i=\max_{j=1}^{n} nxt(F_{i-j},j)$ 。 其中 $nxt(pos,val)$ 表示位置为 $pos$ 的严格后方第一个值为 $val$ 的位置。 与此对应的 $pre(pos,val)$ 表示位置为 $pos$ 的非严格前方（也就是可以包含其本身）的最后一个值为 $val$ 的位置（若没有则为 $0$）。 你绞尽脑汁发现怎么想都无法优化，读懂了题解后发现 $cdq$ 分治太牛了。 考虑 $dp$ 转移时用 $cdq$ 分治优化，每次分治先求出 $[l,mid]$ 的答案后计算整个 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。 一些必要的观察： - $F_i >F_{i-1}$，显然。 - $nxt(i,k)\le nxt(i+1,k)$ - 进一步的，上式不取等当且仅当 $a_{i+1}=k$。 - 所以可以发现一定存在一段区间 $i\in[l,r]$的 $nxt(i,j)$ 都相等。这样的极长区间满足 $i\in[l,r] ~~ , a_i\ne j\lor i=l\land a_{r+1}=j$。 - 最重要的优化来了： - 分治时，对于每个 $j$，一定只有 $[l,mid]$ 中的**一段后缀**对 $[mid+1,r]$ 的一些部分有着**相同**的贡献。 - 考虑 $i\in [l,mid]$ 的$nxt(F_i,j)$ 。若 $nxt(F_i,j)\le F_{mid}$ 。则其一定不会对 $[mid+1,r]$ 的部分产生贡献。因为有 $F_{i,i\in [mid+1,r]} >F_{mid}$ 。 - 而若 $nxt(F_i,j)>F_{mid}\land F_i<F_{mid}$ 则说明 $nxt(F_i,j)=nxt(F_{mid},j)$ 。 - 所以只用找到 $[l,mid]$ 中，第一个满足 $nxt(F_i,j)>F_{mid}$ 的点 $k$。这个点显然是 $\max(l,pre(F_{mid},j))$ 。 - 则 $i\in[k,mid]$, $F_{i+j}=\max(F_{i+j},nxt(F_{i},j))$ 。这里的所有 $nxt(F_i,j)$ 都与 $nxt(F_{mid},j)$ 相等。且若 $i+j\le mid$ 是没有影响的，因为之前分治的时候一定已经统计了这部分的贡献，重复贡献显然是无所谓的。 - 这个形式如同区间对一个数 $checkmax$，但其实不用上线段树维护。 - 考虑将这段区间 $[k+j,r]$ 直接变为全局的一段后缀 $[k+j,sum]$ 。显然是没有影响的，因为 $F_{i+1}>F_{i}$ 。 - 所以这个后缀 $checkmax$ 可以直接将标记打在 $k+j$ 这个位置，然后 $F$ 取前缀 $\max$ 即可。 - 进一步的，你发现取前缀 $\max$ 根本就是屁用没有的操作，因为 $F_i$ 是严格大于 $F_{i-1}$ 的。 - 所以对于每个 $j$ 有效的贡献就只有 $F_{k+j}=\max(F_{k+j},nxt(F_{k},j))$ 。 分析一下时间复杂度。每次求 $pre,nxt$ 可以在每个值对应的下标序列的 $vector$ 中二分 $\log n$ 求出。 cdq 分治每一层枚举的 $j$ 一定只能在 $[1,r-l]$ 之间（直接近似看作区间长度）。所以总复杂度 $O(sum \log sum \log n)$。 ### [P3295 [SCOI2016] 萌萌哒](https://www.luogu.com.cn/problem/P3295) 区别于之前写的简单好写的 st表优化并查集 $O(n\log n)$做法，这次写的是 lxl 之前上课讲的支持在线的 $O(n\log^2 n)$做法。 考虑优化暴力的 $O(nq)$ 的并查集暴力连边。 用一个线段树维护关于并查集的哈希值，以此快速判断两个区间的并查集状态是否相等。 这要求我们维护并查集时必须保证 $f[x]$ 的值就是 $find(x)$ 的值，也就是并查集树最多只有两层。 考虑每次操作暴力二分 $LCP$ 然后修改下一位。修改时启发式合并，将所有被合并的 $siz$小的部分的位置的 $f$ 数组都改为 $siz$ 更大的部分的 $f$ 数组。这个也要在线段树上进行修改。 均摊复杂度 $O(n \log^2 n)$。 ### [gym104030K](https://codeforces.com/gym/104030/problem/K) & [T436388 回文串问题（palin）](https://www.luogu.com.cn/problem/T436388) &[QOJ 4998 Keyboard Queries](https://qoj.ac/problem/4998) 上面一道题的变式。 答案为 ```Not equal``` 当且仅当询问的两个区间长度不相同。 一个串为回文串的信息意味着关于对称轴的对称位置都相等。 线段树维护一个从左向右，以及一个从右到左的哈希值即可快速判断。 出题人卡哈希素质极差。写了自然溢出+取模哈希才能过。 ### [QOJ 9904 最小生成树](https://qoj.ac/problem/4998) 完全图求 MST 第一反应可能是 boruvka。 但是因为边权不是 $a_i+a_j$ 而是 $a_{i+j}$ ，这样会使每轮找最优出边时非常困难。 不妨换个思路，用 kruskal。 对 $a$ 进行从小到大的值域扫描线（说人话就是从小到大排序）。 然后发现连边的形式就是一段 前缀/后缀 关于其对称轴两两连边，和上面那个回文串的连边形式很像，同样用线段树维护正反方向哈希值然后二分 $LCP$ 修改，并查集启发式合并即可。 时间复杂度 $O(n\log ^2n)$。有高妙的 [$O(n\log n )$ 做法](https://www.cnblogs.com/binbin200811/p/18698464)，但是现在还没看懂捏。 ### [P11392 [JOI Open 2019] 三级跳](https://www.luogu.com.cn/problem/P11392) 考虑支配集做法，去掉无用的贡献。 因为关于答案的贡献形式是一个 $3$ 元组 $ (a,b,c),a<b<c\land b-a\le c-b,$ $ans=\max(ans,A_a+A_b+A_c)$ 考虑固定其中一项或两项，然后求其余项的最优贡献。兜兜转转后发现固定 $a,b$,然后在 $c$ 上查询是最容易的。 对于一组固定的 $(a,b)$，会对 $[2b-a，n]$ 这一段的 $c$ 产生贡献，发现这是一段后缀 $chkmax$ 的操作。所以若查询区间 $[L,R]$ 中的 $a_i,a_j,b_i,b_j$ 出现 $2 b_i-a_i\ge2b_j-a_j \land (A_{a_i}+A_{b_i})\le (A_{a_j}+A_{b_j})$，则 $(a_i,b_i)$ 被 $(a_j,b_j)$ 支配。 考虑 $x<y<z$,按 $A_x,A_y,A_z$ 的大小关系分讨支配发生的情况。 - $A_x\le A_y \le A_z$，则 $(x,z)$ 被 $(y,z)$ 支配。 - $A_x \ge A_y \ge A_z$，则 $(x,z)$ 被 $(x,y)$ 支配。 - $A_y\ge A_x\land A_y \ge A_z$，则 $(x,z)$ 被 $(x,y)$ 和 $(y,z)$ 支配。 - $A_y<A_x\land A_y <A_z$，并无明显的支配情况发生。 事实以上结论的限制已经很强了：对于一组 $(x,y)$ 若 $(x,y)$ 之间存在大于等于 $A_x$ 或 $A_y$ 的点则 $(x,y)$ 一定会被支配。这说明对于一个固定的 $x$，只需要找到其左右两侧最接近 $x$ 的满足 $A_y\ge A_x$ 的位置 $y$ 。这样的 $(x,y)$ 就能覆盖所有的支配情况。 Q:满足 $x<z<y$ 的点 $z$ 并没有被 $(x,y)$ 支配，为何考虑 $x$时不加入 $(x,z)$,$(z,y)$ 呢？ A:因为在考虑 $z$ 的时候若 $(x,z)$/$(z,y)$ 没有被支配，则其一定会被加入支配点集。 这意味着支配点的总数是 $O(n)$ 级别的！ 于是单调栈求出支配点后直接上传统艺能 扫描线+线段树维护答案即可。注意扫描线要从右往左扫，因为你维护的$c$ 是右端点的答案。 线段树要维护：二元组序列 $(X_a,X_b)$ 。初始 $X_a=A_a,X_b=0$ 每次操作对一段后缀的 $X_b ~~ chkmax$ 上一个值，每次查询查询一个前缀的 $X_a+X_b$ 的最大值。 一开始写了一个线段维护颜色段均摊的莫名奇妙的玩意。过了之后开题解发现其实正常线段树就可以直接维护。具体的，```mx(u)``` 表示线段包含节点 $u$ 的最大 $chkmax$ 标记。```mxa(u)``` 表示节点 ```u``` 范围内的 $X_a$ 的最大值。每次修改时有节点维护的答案 ```ans(u)=max(ans(u),mxa(u)+mx(u))```，这里不取等的原因是因为 ```ans(u)``` 还可以来自子节点的贡献。然后正常 ```pushup``` ```pushdown``` 即可。注意 ```pushup``` 时不能修改标记 ```mx```。 ### [P7712 [Ynoi2077] hlcpq](https://www.luogu.com.cn/problem/P7712) 发现问题等价于相交的线段连边，然后判断每一条线段的代表点是否为割点。 考虑扫描线+主席树优化建图。建图时有个小技巧：直接将所有水平线段的 $L,R$ 都加上 $n$。这样就不用水平连竖直，竖直连水平各建一颗主席树了。这样就只用正常扫描线,建一颗主席树。 然后你发现直接在主席树上跑 tarjan 求割点会直接爆炸。因为辅助虚点会影响图的形态，使得原本某些是割点的点在这个图上不是割点，而虚点“代替”其成为割点。 考虑分析正常 tarjan 求割点的代码 ```cpp void tarjan(int u){ int ct=0; for(int v:E[u])if(!dfn[v]){ tarjan(v),++ct,cmin(low[u],low[v]); if(low[v]==dfn[u])iscut[v]=1; }else low[u]=min(low[u],dfn[v]); if(u==rt)iscut[x]=ct>1; } ``` 考虑 ```if(!dfn[v])``` 以下的部分只会最多执行 $n$ 次。所以可以快速在主席树上找到 $dfn$ 为 $0$ 的点，至于第二部分等价于 $low[u]$ 与所有 $u$ 能到的点 $v$ 的 $dfn[v]$ $chkmax$。这一部分直接隐式建边就可以维护。 然后你发现因为这是主席树，而不是普通的线段树，这一切都炸完了。因为主席树上的一个节点可能有很多个父亲节点。如果每次修改都暴力维护其所有父亲节点的信息然后继续这样暴力 $pushup$ 复杂度直接升天。 考虑这样一个事情： - 定义 $mn(u)$ 表示主席树上节点 $u$ 对应范围的当前最小的 $dfn$ 。 - 定义 $exist(u)$ 表示主席树上节点 $u$ 对应范围的所有满足 $dfn_v= 0$ 的 $v$ 的数量之和。 - 我们的目标是每次查询时都能得到正确的 $mn(u)$ 与 $exist(u)$。 - 考虑若当前主席上的一个节点 $u$ 的$exist(u)=0$，则以后的所有更新都不会影响到 $u$。而因为 tarjan 是一个 $dfs$ 的过程所以每次每个节点回溯时其所有的邻域的 $dfn$ 都不为 $0$。这说明等到最后 $qry(L[u],R[u],root[u])$的时候主席树对应版本的所有节点的 $exist$ 都为 $0$。 - 也就是说若我们能保证当 $exist(u)=0$ 的时候点 $u$ 的信息能正确维护就行了。 直接用文字不太好说清楚，结合代码说吧： ```cpp struct tree{int ls,rs,mn,exist;}tr[N*45]; int cur; #define mid ((l+r)>>1) #define ls(u) tr[(u)].ls #define rs(u) tr[(u)].rs #define mn(u) tr[(u)].mn #define exist(u) tr[(u)].exist void upd(int x,int type,int &u,int v,int l=1,int r=m){ tr[u=++cur]=tr[v];exist(u)+=type; if(l==r){if(type==1)pos[x]=u;return;} if(x<=mid)upd(x,type,ls(u),ls(v),l,mid); else upd(x,type,rs(u),rs(v),mid+1,r); } ``` 主席树正常建树，$pos[x]$ 表示点 $x$ 对应的主席树叶子节点（由于题目保证无线段共线，所以主席树一个叶子节点只会对应一个点）。 ```cpp int qry(int ql,int qr,int u,int l=1,int r=m){ if(ql<=l&&r<=qr)return mn(u); int res=inf; if(ql<=mid)cmin(res,qry(ql,qr,ls(u),l,mid)); if(mid<qr)cmin(res,qry(ql,qr,rs(u),mid+1,r)); return res; } ``` 查询最小的 $dfn$ 部分非常简单。 ```cpp int find(int ql,int qr,int u,int l=1,int r=m){ if(!exist(u))return 0; if(l==r)return l; int res=0; if(ql<=mid) res=find(ql,qr,ls(u),l,mid); if(mid<qr&&!res) res=find(ql,qr,rs(u),mid+1,r); if(!exist(ls(u))&&!exist(rs(u))) exist(u)=0,mn(u)=min(mn(ls(u)),mn(rs(u))); return res; } void tarjan(int u){ int ct=0,v; SGT::exist(pos[u])=0;SGT::mn(pos[u])=dfn[u]=low[u]=++cnt; while((v=SGT::find(L[u],R[u],root[u]))){ tarjan(v);++ct;cmin(low[u],low[v]); if(low[v]==dfn[u]&&u!=tart)iscut[u]=1; } cmin(low[u],SGT::qry(L[u],R[u],root[u])); if(u==tart)iscut[u]=ct>1; } ``` tarjan 部分与 find 部分一起分析。 - 思路大概是每一个点随时获取其子节点的信息，而不是子节点向所有父节点上传信息。 - 所以在 tarjan 时 ```SGT::exist(pos[u])=0;SGT::mn(pos[u])=dfn[u]=low[u]=++cnt;``` ，即修改对应叶子节点的信息。 - find 时```if(!exist(ls(u))&&!exist(rs(u))) exist(u)=0,mn(u)=min(mn(ls(u)),mn(rs(u)));```，即如果所有子节点的信息都已经确定了，就确定当前点的信息。 分析一下时间复杂度。“有效” find 与“无效” find (是否找到 $dfn$ 为 $0$ 的点) 分别分析。 - “有效” find,最多有 $O(n)$ 次,单次 $O(\log n)$。总共 $O(n\log n)$ 。 - “无效” find,每次“无效”find 会把所有的进入过的主席树节点的信息都确定下来。每次进入的一定是没有确定信息的点（若信息确定,即 ```!exist(u)``` 就直接 ```return ;``` 了）。而主席树的总节点数是 $O(n \log n)$ 的。所以最多进行 $O(n\log n)$ 次。 所以此题总复杂度 $O(n\log n)$。 ps: ```cpp struct tree{int ls=0,rs=0,mn=inf,exist=0;}tr[N*45]; ``` 这样写会直接炸掉，因为编译器编译前会将其展开成 $N\times 45$ 个赋值语句，导致代码过长然后 CE。所以最好不要在主函数外初始化。 总结： - 经典trick：扫描线+主席树优化建图 - 建图小trick：将前 $n$ 个点的 $L,R$ 都 $+n$ 从而去掉一颗主席树 - 思路非常巧妙但有些 Ad_hoc 的 tarjan 与 find。 ### [P4899 [IOI 2018] werewolf 狼人](https://www.luogu.com.cn/problem/P4899) 终于把这个典题写了。 考虑分别对人形态与狼形态建出最大/最小 kruskal 重构树。每个形态可行的范围一定是重构树上一棵子树，对应子树可以用树上倍增简单求出。 现在问题转化为判断两棵子树是否有交。考虑将点按第一棵树的 $dfn$序 置换。这样问题就变为判断第二棵树的一个子树内是否出现过区间 $[L,R]$ 的元素，直接上主席树即可。 [P11160 【MX-X6-T6】機械生命体](https://www.luogu.com.cn/problem/P11160) lxl 讲课D2T3 因为操作与 $lowbit$ 密切相关，所以考虑从低位到高位建立 $Trie$ 树。（ [AT_agc044_c [AGC044C] Strange Dance](https://www.luogu.com.cn/problem/AT_agc044_c) 也是从低到高建树的。） 加入与删除是好做的，而查询也是直接在 $Trie$ 树上走下去即可。唯一棘手的是操作三。 操作 $3$ 可以看作对 $Trie$ 上的一棵子树加 $v$ 。直接想感觉非常困难。不妨先考虑全局。 - 全局 $+1$：交换 $0,1$ 两棵子树，然后在**交换后** 的 $0$ 子树上继续进行 $+1$ 操作。不难发现这是一个单侧递归形式的问题。 - 全局 $+2k$: 在 $0,1$ 子树上分别加上 $k$。 - 全局 $+2k+1$ :先进行全局 $+1$，再进行全局 $+2k$ 。 - 不难发现加操作可以通过打 $tag$ 实现操作压缩。 会了全局加 $v$ 后发现子树加仍然是困难的，因为加的不一定是对应的 $2^k$ 的倍数。 既然全局是好做的，能不能把问题转为全局呢？是可以的。我们按照类似线段树的合并与分裂的操作，先将要加的子树分裂出来，打上全局加的 $tag$，然后再合并回去，就行了。（这个思路还是非常巧妙的） ### [P4525 【模板】自适应辛普森法 1](https://www.luogu.com.cn/problem/P4525) 基本思路：用特定函数去拟合给定函数，然后求积分。但肯定不能全局拟合，这样误差会非常大。考虑分很多部分分别拟合，然后对每个部分的答案求和。 基本框架： ```cpp db solve(db l,db r,db eps,db S0){ db mid=(l+r)/2,S1=calc(l,mid),S2=calc(mid,r); return equal(S0,S1+S2,eps)?S0:solve(l,mid,eps/2,S1)+solve(mid,r,eps/2,S2); } ``` 就是说考虑计算当前区间与左右区间分别的答案，若相差在精度要求内就直接返回结果，否则递归求解。（这就是“自适应”） 一下的拟合区别在于 $calc$ 函数的实现。 #### 用一次函数拟合： 这个是简单的，直接转化为梯形算面积就完了。 ```calc(l,r)=(r-l)/2+(F(l)+F(r));``` #### 用二次函数拟合 设当前区间拟合的函数为 $F(x)=Ax^2+Bx+C$。 则： $\int_{l}^{r}F(x) dx= \frac{A}{3}(r^3-l^3)+\frac{B}{2}(r^2-l^2)+C(r-l)$ = $\frac{r-l}{6}(2A(r^2+lr+l^2)+3B(r+l)+6C)$ = $\frac{r-l}{6}[(Ar^2+Br+C)+(Al^2+Bl+C)+(Ar^2+Al^ 2+2Alr+2B(l+r)+4C)]$ = $\frac{r-l}{6}[(Ar^2+Br+C)+(Al^2+Bl+C)+4\times(A\frac{r^2+2lr+l^2}{4}+B\frac{(l+r)}{2}+4C)]$ = $\frac{r-l}{6}[F(r)+F(l)+4\times F(\frac{l+r}{2})]$ 二次函数拟合的推出来结果也就是辛普森公式。 版题直接套公式就完了，一次二次拟合都随便过。 ### [SP8073 CIRU - The area of the union of circle](https://www.luogu.com.cn/problem/SP8073) 圆的面积并。 此题考虑设计函数 $F(k)$ 表示所有圆与直线 $x=k$ 的交的并。显然答案就是对 $F$ 求积分。 因为圆的个数不多，所以考虑每次调用 $F$ 是暴力计算。 但会出现问题，就是直接以全局的最左/最右点为 $[L,R]$ 来计算积分很可能根本不会扫到一些很小的圆（反映在函数 $F$上就是一段很小的增减性变化可能没有考虑到）。所以考虑分段计算，可以按每个圆的左右端点分段，然后每一段分别计算。最后注意去除被其他圆包含的圆来优化常数。 因为是圆，所以直观上用二次函数拟合比一次函数更好，事实也的确如此。 ## 李超线段树 & 斜率优化 ### [P4097 【模板】李超线段树](https://www.luogu.com.cn/problem/P4097) 李超线段树感觉就是单侧递归+标记永久化。 每个区间都有一个所谓的“优势线段” 直接从oiwiki上贺的图:  显然非优势线段只可能在 $[l,mid]$ 或 $[mid+1,r]$ 中的一个子区间成为更优的线段，所以每次单侧递归。查询时单点查，利用标记永久化把所有走到的区间的标记都查一遍即可。 全局插入直线单次 $O(log n)$，插入线段先找到对应区间，然后分别做单侧递归，单次时间 $O(log ^2n)$ ，但是常数很小。 写模板题时要注意虽然插入的线段编号是从小到大，但是每次比较仍然要判断编号，因为有可能之前编号小的线段被替换下来继续进行单侧递归下方标记。 ### [P5785 [SDOI2012] 任务安排](https://www.luogu.com.cn/problem/P5785) $dp_i$ 表示完成了 $i$ 个任务，同时考虑了耗时对之后加工的影响的最小代价。 对 $t$ 自己求一遍前缀和，$f$ 自己求一遍后缀和，有 $dp$ 转移 : $dp_i=\min_{j=0}^{i} dp_j+(t_i-t_j+s)\times f_{j+1}$ 拆开，整理得： $dp_i=\min_{j=0}^{i} (t_i+s)\times f_{j+1}+dp_j-t_j\times f_{j+1}$ 可以把转移看作在求所有斜率为 $f_{j+1}$，截距为 $dp_j-t_j\times f_{j+1}$ 的直线中取 $x=t_i+s$ 时的最小值。 于是这个用李超线段树可以直接维护。 写完后发现 [P10979 任务安排 2](https://www.luogu.com.cn/problem/P10979) & [P2365 任务安排](https://www.luogu.com.cn/problem/P2365) 两个弱化版都过了，但是本题 70pts,为什么呢？ 因为本题的 $t_i$ 可能为负数！也就意味着求前缀和后 $t_i$ 可能不是单调递增的（就是维护的定义域可能不单调递增）！ 所以应该先按 $t_i$ 排序后才能直接维护，查询时找到对应的 $t_i$ 在哪里，然后再查询。 ### [P2120 [ZJOI2007] 仓库建设](https://www.luogu.com.cn/problem/P2120) 很简单就可以把斜优式子推出来，不用写重排序，写完被 $hack$ 了。 原因是可能最后一个仓库存货量为 $0$。 于是记最后一个有存货量的仓库为 $lst$。答案应为 $\min_{i=lst}^{n} dp_i$。(为什么不直接是 $dp_{lst}$？因为可能后面的仓库建设费用更低从而更优) ### [P4655 [CEOI 2017] Building Bridges](https://www.luogu.com.cn/problem/P4655) 板子题，李超树维护按 $h$ 排序后对应位置的答案即可。注意 $dp$ 时下标从 $2$ 开始转移。 ### [P3628 [APIO2010] 特别行动队](https://www.luogu.com.cn/problem/P3628) 这次不用重排序了，因为 $x_i$ 的前缀和单调递增。 ### [P4360 [CEOI 2004] 锯木厂选址](https://www.luogu.com.cn/problem/P4360) & [SP17877 SAWMILL - Two Swamills](https://www.luogu.com.cn/problem/SP17877) 做法1：先考虑 $n^2$ 枚举选哪两个，然后发现第一个选的对第二个的贡献形式与斜率优化类似。 做法2：不难发现随着第一个位置的右移，第二个位置一定单调不降，上决策单调性分治即可。 ### [P6047 丝之割](https://www.luogu.com.cn/problem/P6047) 比较重要的观察：  满足 $u_i\le u_j\land v_j\le v_i$ 的弦 $j$ 被弦 $i$ 支配。上图中的蓝色弦将其穿过的红色弦支配。 我们用单调栈求出所有的支配弦，则这些弦一定无交（就是为了这一步，否则 $dp$ 转移中会有对 $u,v$ 的 rmq ，无法直接上斜优）。 按照 $u,v$ 其中一维排序后直接上李超树斜优即可。 ### [P4069 [SDOI2016] 游戏](https://www.luogu.com.cn/problem/P4069) 粪题。 考虑树剖，然后修改相当于链上赋值一次函数。 因为每条重链是独立的，所以我们把点到根的 $dis$ 当作定义域建李超树，满足每条重链的定义域是递增的，用李超树维护不会出问题。 每次修改按 $u\to lca$ 与 $v \to lca$ 分别赋值，两次赋值 $a$ 相反，$b$ 稍微推一下即可。 所以单次链修改: 树剖 $O(\log n)$ $\times$ 李超树区间插入线段 $O(\log^2 n)$=$O(\log^3 n)$。 考虑查询，每个线段树节点维护考虑子树内所有标记的最小值 ```mn```。显然 ```pushup``` 时只用考虑左右儿子的答案，以及这个节点所维护的区间的 $[l,r]$ 的两个端点在当前标记上的取值。但是如果只求所有 ```mn```的最小值没有考虑到来自祖先节点的标记的贡献。 考虑在查询时计算这部分贡献，有个非常巧妙的写法： ```ckmin(res,tr[u].get(max(ql,l)));``` ```ckmin(res,tr[u].get(min(qr,r)));``` 因为直线具有单调性，所以最值一定来自范围内的两端，这样写完美实现。 所以单次区间查询 $O(\log n)$，单次链查 $O(\log^2 n)$。 此题总复杂度 $O(m\log^3 n)$。但是因为树剖与李超树常数都巨小所以单个点最慢跑了```136ms```。 ### [P11343 [KTSC 2023 R1] 出租车旅行](https://www.luogu.com.cn/problem/P11343) lxl D3T3。 考虑合理的乘车策略，一定是 $s\to u_1\to u_2\to u_3 \to \dots \to u_k \to t$,其中 $u_1$ 到 $u_k$ 的 $B$ 都单调递减。所以我们一定是按照 $B$ 从大到小转移(不难发现除了起点其它 $B>B_s$ 的点一定不会作为中转点)。 因为费用形如一次函数，所以考虑李超树。 因为与树上距离有关，所以考虑点分治。 考虑建出点分树，对于每个点都开一颗动态开点李超树。还是用标记永久化的思想，每次修改更新点分树上所有的祖先，每次查询查询点分树上所有祖先的标记（查询与修改时都将对应的 $dis(root_{cur},u)$ 考虑在内）。 最后获取答案时再将所有点查询一遍即可。 交互题注意传参类型，盲目```#define int long long ``` 要 ```CE```。 ### [P5391 [Cnoi2019] 青染之心](https://www.luogu.com.cn/problem/P5391) 考虑建出操作树后暴力 $dfs$ 背包硬做，时间 $O(n^2)$ 可行。但是空间 $O(n^2)$ 不可接受。 注意到如果单独求一条链的答案，可以只用一个数组滚动求出答案。但问题是这个操作是不可逆的，迫使我们解决本题时需要在分岔口处记录下当前的 $dp$ 数组的状态。 考虑重链剖分，每次先走轻儿子（每次走到一条重链的顶端时新建一个数组）。走完之后再走重儿子。因为重剖的性质，每个点到根经过的轻边不超过 $\log n$ 条，换句话说就是每个点到根的重链不超过 $\log n$ 条，于是只用开 $\log n$ 个 $dp$ 数组就可以了，空间复杂度为 $O(n\log n)$ 。 注意:有些写法操作树是以 $0$ 为根的。 ### [P7357 「PMOI-1」中位数](https://www.luogu.com.cn/problem/P7357) 考虑 [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839) 的trick，值域扫描线建出主席树，将 $root[v]$ 这个版本中 $\le v$ 的所有值的位置都赋值为 $-1$。其余位置置为 $1$ 。 考虑维护树上每个点到根的点权和。则单点从 $1$ 更新为 $-1$ 时相当于子树 $-2$ 。每次二分 $check$ 时求出两颗子树内的最大值然后用树上差分基本思路减去 $lca$ 于 $fa_{lca}$ 的贡献。 考虑这个题带修异或上 $1$ 非常奇特。仔细分析发现只会影响两个版本的值。于是可以直接做。 还要注意此题空间限制比较紧，要使用标记永久化来优化空间。 ### [P9139 [THUPC 2023 初赛] 喵了个喵 II](https://www.luogu.com.cn/problem/P9139) 不知道这个题为什么调一晚上。 考虑如果只有 $2n$ 个数怎么做。显然若出现 $abba$ 这样的“包含”关系则无解。 考虑 $4n$ 的分配方式（以下数字为出现位置大小，同一括号内的表示对应位置赋值为 $0,1$）： - $<1,2>~~<3,4>$ - $<1,3>~~<2,4>$ - $<1,4>~~<2,3>$ 实际上稍微分析一下就发现这一种划分严格不优于前两种。 所以真正有有意义的取值只有两种 $!$ 两种自然会想到 $2-sat$。 考虑矛盾就是包含关系。处理这个可以扫描线+主席树优化建图。于是写两棵主席树一颗处理包含，一颗处理被包含即可。 最后发现大小为 $1e7$ 左右的 $vector$ 非常慢，于是改成链式前向星就快了很多。 注意：主席树上新的点既要向原来的点连边，也要继承原来点的左右儿子。 ### [0410 BSZX联考T2](https://vjudge.net/problem/CodeChef-TREEQUER) & [OJ7链接](http://i.oj7.top/problem/1495) $O(n\sqrt{n\log n})$ 1.5s 暴冲 $5e5$，没被卡，嘻。 考虑问题等价于求这些点形成的联通块个数。 考虑暴力，我们钦定每个联通块的代表点为深度最浅的那个点。若一个点的父亲节点没有在给定点集中，则这个点为代表点。 用 $dfn$ 序置换掉原来的点的编号，然后： - 考虑暴力，单次 $\sum_{i=1}^{k} r_i-l_i+1$，可以看作 $O(n)$ 。 - 父亲节点没出现的点的个数=点集中点的总数-父亲节点出现过的点的个数。 - 考虑当 $k=1$ 时，等价于求满足 $i \in[l,r]\land fa_i \in [l,r]$ 的 $i$ 的数量，把 $fa$ 数组看成序列，等价于求下标在 $[l,r]$ 中的满足值在 $[l,r]$ 中的数的个数，可以用主席树轻松实现，单次 $O(\log n)$。 - 考虑当 $k>1$ 时，可以暴力枚举区间，求区间对区间的贡献，复杂度 $O(k^2 \log n)$ 。 - 自然的，考虑根号分治把暴力与主席树做法拼起来，得到 $O(n\sqrt{n\log n})$ 的总复杂度。 实际上手造对着阈值硬卡的数据可以跑到 1.6s，但是搬题人没卡导致跑得比某些 $O(n\log n)$ 的做法还快。 ### [P5508 寻宝](https://www.luogu.com.cn/problem/P5508) 把边分为两类：给定的与打隧道打通的。 发现第一类可以用线段树优化建图简单实现。 第二类可以用李超树实现,需要以下功能： - 插入线段。 - 毙掉一个点的贡献。 - 求全局最小值的点的值及其编号。 因为求极值依然是尽可能取左右两端，所以考虑李超树上每个节点维护当前合法的 $nl,nr$。每次毙点暴力更新 $nl,nr$。均摊复杂度 $O(n\log n)$。 每次跑 $dij$ 的时候判断堆顶与李超树的全局最小值哪个更小就用哪个。 需要注意的一些细节： - 通过李超树得到的点要更新对应的 $dis$ 数组。 - 打印结果时忽略线段树优化建图的虚点。 ### [P2305 [NOI2014] 购票](https://www.luogu.com.cn/problem/P2305) 朴素 $dp$ 式子： 设 $S$ 为 $u$ 的祖先集合，$d_x$ 为点 $x$ 到根的距离的前缀和，有： $dp_u=\min \limits_{v \in S\land d_u-d_v\le l_u} dp_v+q_u+p_u(d_u-d_v)$ $~~~~~~~=\min \limits_{v \in S\land d_u-d_v\le l_u} dp_v+q_u+p_ud_u-p_ud_v)$ 发现如果去掉限制是斜率优化的转移形式，可以用李超树实现。 考虑 $v \in S\land d_u-d_v\le l_u$ 这两条限制都可以转化为有关 $dfn_v$ 的限制。考虑使用树剖+线段树套李超树实现。每次插入直接在$dfn$ 对应的外层线段树节点上插入直线，查询时是在树剖分成的不超过 $\log n$ 个 $dfn$ 区间的外层线段树上查询当 $x=p_u$ 时内层李超树的最小值。 这样做总的插入的空间复杂度是 $O(n\log n\log V)$ ($V$为 $p$ 的值域)，总的查询复杂度为 $O(n\log n^2 \log V)$ 。空间复杂度为 $O(n\log n)$ （李超树的空间复杂度不超过总的插入直线条数）。 接下来给出一种利用出栈序（dfn序的反序）实现的总查询 $O(n\log n\log V)$ 的做法(虽然理论复杂度更优，但实际表现与树剖基本相同，胜在码量更短)： - 考虑 $dfn$ 与子树有很强的关系，一棵子树可以划分为一段连续的 $dfn$ 序。 - 若我们先访问 $dfn$ 序更靠后的子树（即按出栈序访问），查询祖先有关信息就可以直接在祖先到其节点的 $dfn$ 区间上查询，而 $dfn$ 序中间“夹”着的兄弟子树因为还没访问到所以信息为空，不会影响答案。 ### 一些细节： - 找深度最浅的满足条件的祖先不用树上倍增，深搜时维护一个记录当前根链信息的栈，然后直接在栈里二分即可。 - 李超树的定义域为 $p$ 的值域，开到 $1e6$ 即可。不要像某个唐人一样迷糊地开到 $2e11$，然后发现插入直线时计算过程会爆 ```long long```。 --- ## 二维分块 ### [U210802 人类智慧分块](https://www.luogu.com.cn/problem/U210802) $O(\sqrt n)$ 加点 $O(1)$ 查 以及 $O(1)$ 加点 $O(\sqrt n)$ 查。$n$ 是坐标的值域，这要求点/查询的矩形有一定特殊的性质，下面说明 $O(\sqrt n)$ 加点，$O(1)$ 查的二维分块，另外一种本质相同。 贺几张大佬 @[Cat_shao](https://www.luogu.com.cn/user/234011) 的图\bx  我们将平面划分成 $n^{\frac 1 2}$ 个边长为 $n^{\frac 3 4}$ 的橙色大正方形，**所有的橙色大正方形视为一个部分**。 然后将每个橙色大正方形分成 $n^{\frac 1 2}$ 个边长为 $n^{\frac 1 2}$ 的蓝色小正方形，平面上共有 $n$ 则个蓝色小正方形。**所有位于同一个橙色大正方形的蓝色小正方形视为一个部分**。  将平面分为 $n^{\frac 3 4} $个 $n^{\frac 3 4} \times n^{\frac 1 2}$ 的黄色扁条矩形。从下到上依次划分成 $n^{\frac 1 4}$ 个 $n\times n^{\frac 3 4}$ 的部分，**每个部分有 $n^{\frac 1 2}$ 个黄色扁条矩形。（每一部分的黄块的并是一整行的橙块）**  将平面分为 $n^{\frac 3 4} $个 $n^{\frac 1 2} \times n^{\frac 3 4}$ 的绿色长条矩形。从左到右依次划分成 $n^{\frac 1 4}$ 个 $n^{\frac 3 4} \times n$ 的部分，**每个部分有 $n^{\frac 1 2}$ 个绿色长条矩形。（每一部分的绿块的并是一列橙块）** 发现每个点所在的橙色，蓝色，黄色，绿色矩形的所在部分都只有 $n^{\frac 1 2}$ 个同类矩形。我们对于**每个部分**都**独立维护**前缀和。 查询时可以划分成下图的样子：  容易发现除了紫色的零散部分其他每种颜色的贡献都可以 $O(1)$ 得到（单点修时 $O(\sqrt n)$ 进行后缀加）。 考虑紫色部分的贡献。这个时候可以运用题目给的性质：所有点的 $x,y$ 坐标都互不相同。这意味着点在紫色部分的分布是**非常稀疏**的，一定不超过 $O(\sqrt n)$ 级别。 因为要 $O(1)$ 查还是考虑用反演的方式去看一个点可以对哪些矩形产生贡献。  我们将 $x$ 轴与 $y$ 轴分块，块长 $\sqrt n$ 。这里以 $y$ 轴为例进行讲解。 我们对每个块开个 ```vector``` 存储顶点在这个块内的矩形的信息。对于一个点 $(x,y)$，其会对块内满足 $x\le u,y\le v$ 的矩形产生贡献。我们暴力枚举所有块内的矩形依次判断即可。我们从矩形顶点的角度分析复杂度，一个矩形顶点最多与 $\sqrt n$ 个点位于同一块内。所以总复杂度 $O(m\sqrt n)$($m$ 为矩形个数)。 ### 一些细节： - 最好令 $n\gets \lceil n^{\frac 1 4}\rceil ^{4}$，使得 $n^{\frac 1 2}$ 一定是 $n^{\frac 1 4}$ 的整数倍数。不然不同颜色的块之间可能出现交叉重叠。 - 某些查询不能考虑 蓝块/黄块/绿块 的贡献。 - 散块的点中 $x$ 与 $u$ 在同一块且 $y$ 与 $v$ 在同一块中的这种点的贡献不能算重。 --- ### [P7448 [Ynoi2007] rdiq](https://www.luogu.com.cn/problem/P7448) & [区间本质不同逆序对](https://www.luogu.com.cn/problem/P7601) 考虑弱化版区间逆序对数 [P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 的 $O(n\sqrt m)$ 的莫队做法。 这个题也上莫队，考虑转移。考虑当前莫队区间 $[l,r-1]$ 转移到 $[l,r]$ (其余情况同理)。记最大的满足 $a_x=a_r$ 的 $x$ 为 $pre_r$（若没有则为 $0$）。 则只有 $[\max(l,pre_r+1),r-1]$ 的部分的数能产生贡献。 所以最后能产生贡献的位置 $i$ 应满足 $pre_i<l~\land i\in [\max(l,pre_r+1),r-1] ~ \land a_i<a_r$。 考虑这是一个三维偏序的形式，我们可以通过扫描线+莫队二次离线干掉 $pre_i<l$ 这一维（从右往左扫,只保留每个数最靠左出现的位置）。 然后剩下的两维可以简单差分一下表示成两个 $2-side$ 矩形。用之前说的二维分块维护即可。 为了让点稀疏，即使$x,y$ 互不相同，我们考虑将序列离散化成一个排列，满足相同的数离散化后的值靠左的比靠右的更小（容易发现这样不会影响答案）。 ### [P8530 [Ynoi2003] 博丽灵梦](https://www.luogu.com.cn/problem/P8530) 第一反应的四维莫队可以得 60pts。 然后说正经莫队： 考虑对 $l_1,r_1$ 这一维莫队，然后维护每个相同颜色的点在 $p$ 上的前驱/后继。 考虑加入点用 $set$ 带 $\log$，但删除点可以 $O(1)$ 做，于是考虑回滚莫队。 查询即查满足 $pre_{p_i}<l_2~ \land l_2\le p_i\le r_2$ 的 $b_{a_i}$ 的和。这个也可以差分一下转化为两个 $2-side$ 矩形。可以用 $O(1)$ 加入/删除 点，$O(\sqrt n)$ 查询的二维分块维护。 但注意到会有许多点的 $pre$ 为 $0$。对于所有的这些点单独开一个值域分块维护即可。 ## trick: 神秘模数 $U^V$，值巨小，维护多项式 ### [P12014 [Ynoi April Fool's Round 2025] 牢帽](https://www.luogu.com.cn/problem/P12014) - 考虑 $x=0$, $a$ 不带修。显然线段树分治板子。 - 考虑 $x=0$, $a$ 带修。一种自然的想法是把关于 $a$ 的修改也用线段树分治处理。线段树分治可以处理 "加入"这样的信息。考虑我们初始不算任何点的贡献（即默认点的权值为 $1$）。加入一个点的点权相当于对当前这个点 $k$ 所在联通块乘上 $a_k$。 - 考虑 $U \mid x$ 的做法。则最终每个联通块 $S$ 的贡献为 $\prod_{i\in S} (a_i+x)$ 。考虑这是一个与 $a$ 以及 $x$ 有关的多项式 $p_1x+p_2 x^2 + p_3 x^3\dots$。而且这个多项式有个很好的性质就是对于$x^k$（$k\ge V$）的部分的贡献都是 $0$。而此题中 $V\le 4$。所以可以考虑每次合并直接 $V^2$ 做多项式乘法维护多项式（常数为 $\frac 1 2$）。每次将对应的 $x$ 带入维护的多项式中求值即可。 - 现在考虑 $U\nmid x$ 的情况。考虑到此题中 $U\le 10$。所以我们可以对 $p\in[0,U)$ 中的每一个整数 $p$。都维护一个令 $a_k\gets a_k+p$ 的版本。 所以本题时间复杂度 $O(UV^2q\log q+q\log q\log n)$。 ### [P10175 「OICon-02」Subtree Value](https://www.luogu.com.cn/problem/P10175) 考虑暴力枚举 $\left\vert S \right\vert$。对于每个点跑一遍树形背包状物。复杂度 $O(n^3)$。（关于树形背包的时间复杂度，可以对于每棵子树都考虑最坏的情况然后把贡献拆到点上证明上界是 $n^2$ 的，至于背包体积为 $m$，点体积为 $1$ 的树形背包复杂度为$O(nm)$，笔者现在还不会证。） 因为 $U,V$ 很小，直接用 trick 做即可得到 $O(UV^2 n^2)$ 的复杂度。但是裸的次数有 $1.44e9$ 的运算次数。即使将 $V^2$ 部分的 $\frac 1 2$ 常数算上也有 $7.2e8$ 的次数。时限 $1s$ 根本过不去。 - 把封装的 $poly$ 拆开 $20pts\to 54pts$。（所以之前封装了个寂寞） - 乘的时候加上 ```if(!F[u][i][k]) break;```，就莫名奇妙过了。 --- ## [P5608 [Ynoi2013] 文化课](https://www.luogu.com.cn/problem/P5608) 线段树绝世好题！[最优解拿下！](https://www.luogu.com.cn/record/list?pid=P5608&orderBy=1&status=&page=1) - 考虑不带修。对于加号```pushup```时直接将线段树左右儿子的结果相加即可。乘号的话考虑左右儿子的值的和先减去左儿子极长右侧连乘段的贡献，再减去右儿子左侧极长连乘段的贡献，最后加上上述两个极长连乘段的乘积即可。现在有 $5pts$ 了！ - 考虑只修改符号。对于每个线段树节点都额外维护若这个节点的符号都是加/乘的结果。好现在有 $24pts$ 了！ - 考虑只修改值。对于每个线段的每个节点都维护一个系数非零的多项式 $p_{k_1}x^{k_1} +p_{k_2} x^{k_2}+p_{k_3} x^{k_3} \dots +p_{k_{cnt}}x^{k_{cnt}}$。容易发现 $\sum_{i=1}^{len}p_{k_i}\times k_i=len$。这启示我们 $p$ 的种类数不超过 $O(\sqrt n)$ 级别。考虑线段树上每个节点都开一个```pair<int,int>``` 类型来存储多项式,```pushup``` 时暴力归并求得新的多项式。因为每个节点对应的空间要求不同，所以可以对每个点都开一个 ```vector```，然后```resize```设置可能的最大大小即可。 - 证明一下空间复杂度是 $O(n)$ 的。考虑线段树的每一层。复杂度为 $\sum_{i=0}^{\lceil \log n\rceil} 2^i\times \sqrt{\frac{n}{2^i}}=\sum_{i=0}^{\lceil \log n\rceil} =\sum_{i=0}^{\lceil \log n\rceil} \sqrt{n\times 2^{i}}$。容易发现是公比为 $\sqrt 2$ 的等比数列求，结果大致为 $(1+\sqrt{2n})\sqrt n$。这同时也可以说明```build```时的```pushup```的总复杂度是 $O(n)$ 的。 - 修改直接将新值带入对应节点的多项式求值即可,考虑如果每次每一项都用快速幂求单次求值复杂度可达 $O(\sqrt n\log n)$。这里考虑按照次幂从低到高依次计算，每次快速幂只计算相邻两项的次幂之差。根据[大佬的证明](https://www.luogu.com.cn/article/50b2ynxa)这样做是单次 $O(\sqrt n)$ 的。 - 现在考虑修改符号对多项式的影响。容易发现如果新符号为 $+$，则线段树对应节点的多项式为 $len\times x$。若为$\times$ 则为 $x^{len}$。故对于一个线段树节点单次修改可以做到 $O(1)$。 - 现在说明修改符号后从对应节点一路 ```pushup``` 上去的复杂度是 $O(\sqrt n)$ 的。考虑将修改区间在线段树上表示出来，**则每一层的节点数不超过 $2$**。所以有每一层 ```pushup```的总节点数不超过 $2$。单独考虑每一层的贡献：$(\sum_{i=0}^{\lceil \log n\rceil} \sqrt{\frac{n}{2^i}}\times 2)-\sqrt n$(第一层只有一个点)。容易发现大致为 $(1+\sqrt 2)\sqrt n$。所以是 $O(\sqrt n)$ 的。 所以这题就做完了，时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$。 --- ### [P11519 [CCO 2024] Telephone Plans](https://www.luogu.com.cn/problem/P11519) 注意读题。是所有之前存在过的边都不构成环。并且一条边不会删了又加。 贡献是好推的。问题转化为如何快速合并/分裂两个联通块并维护 $siz$。合并是容易的，直接启发式合并即可。 分裂考虑启发式分裂（第一次遇到qwq）。考虑同时从断边的两个点开始 ```bfs```。一旦一个点 ```bfs``` 完就可以获取到对应 ```siz```。这里很容易写假。我们不能一次性访问完所有点的出边（不然一个菊花就卡掉了）。我们需要一条边一条边的访问。所以我们按照当前弧优化之类的思想。因为存边肯定是用 ```set``` 或者 ```unordered_set``` 存。所以考虑维护每个点的当前迭代器是什么。进一步地，可以直接维护两个队列对头对应的当前弧是什么。 考虑写正常并查集会出问题。因为分裂时大的那部分的根可能在小的那部分中。考虑维护一个始终只有两层的并查集。第一层为虚点代表对应集合，第二层为实际点连向虚点。这样就可以解决上述问题。 写起来有点粪，细节有点多。打算等以后学了 $LCT$ 再来重温一下此题。 --- ## SA后缀数组 ### [P3809 【模板】后缀排序](https://www.luogu.com.cn/problem/P3809) 基于倍增与计数排序，详见 [wiki](https://oi-wiki.org/string/sa/) 好写的 template: ```cpp #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,sa[N],rk[N],id[N],oldrk[N<<1],cnt[N];string s; signed main(){ ios::sync_with_stdio(0);cin.tie(0),cout.tie(0); cin>>s;n=s.length();m=128; for(int i=1;i<=n;++i)++cnt[rk[i]=s[i-1]]; for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1]; for(int i=n;i;--i)sa[cnt[rk[i]]--]=i; for(int w=1,cur,p=0;p<n;w<<=1,m=p){ iota(id+1,id+1+w,n-w+1);cur=w; for(int i=1;i<=n;++i)if(sa[i]>w)id[++cur]=sa[i]-w; fill(cnt+1,cnt+1+m,0);p=0; for(int i=1;i<=n;++i)++cnt[oldrk[i]=rk[i]]; for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1]; for(int i=n;i;--i)sa[cnt[rk[id[i]]]--]=id[i]; for(int i=1;i<=n;++i)rk[sa[i]]=(p+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w])); } for(int i=1;i<=n;++i)cout<<sa[i]<<' ';return 0; } ``` ### [P4051 [JSOI2007] 字符加密](https://www.luogu.com.cn/problem/P4051) 宝宝题。末尾接原串然后跑 $SA$ 即可。 ### [P2870 [USACO07DEC] Best Cow Line G](https://www.luogu.com.cn/problem/P2870) 显然贪心取两端中字典序更小的那一端。唯一的问题是若两端的 $LCP$ 过长如何快速比较大小。将反串接在原串后跑 $SA$ 即可。 ### [P2408 不同子串个数](https://www.luogu.com.cn/problem/P2408) SA 宝宝题。 ### [P4248 [AHOI2013] 差异](https://www.luogu.com.cn/problem/P4248) 考虑想象这样一个图：有 $n$ 个点。$i$ 与 $i+1$ 之前用边权为 $h_i$ 的边相连。定义两点 $u,v$之间的权值 $w(u,v)$ 为点 $u$ 到点 $v$ 之间所有边权值的最小值（即 $LCP(sa_u,sa_v)$）。求所有点对的权值之和。考虑按从大到小的顺序加入边，用并查集维护。 ### [P2178 [NOI2015] 品酒大会](https://www.luogu.com.cn/problem/P2178) 也考虑上题的做法然后按从大到小的顺序加入边。每个联通块要维护其大小，最大/次大非负数，最小/次小负数。 ### [P4081 [USACO17DEC] Standing Out from the Herd P](https://www.luogu.com.cn/problem/P4081) 这个题考虑来自本串的贡献与其他串的贡献。显然其他串的贡献就是与在 $rk$ 上的前驱/后继的 $LCP$ 的最大值。本串的贡献与 [P2408 不同子串个数](https://www.luogu.com.cn/problem/P2408) 相同，即钦定一个顺序加入本串的所有后缀然后找前驱/后继算 $LCP$ 的最大值。考虑串与串之间直接拼接然后SA所求的后缀的 $LCP$ 与原来串的后缀的 $LCP$不一定等价。所以可以在拼接两个串时用一个之前从未出现的字符来连接，这样就对了。 ### [SP1811 LCS](https://www.luogu.com.cn/problem/SP1811) & [SP1812 LCS2](https://www.luogu.com.cn/problem/SP1812) 求最长公共子串。考虑SA 然后做双指针，单调队列维护 $h$ 的最小值。 ### [P1117 [NOI2016] 优秀的拆分](https://www.luogu.com.cn/problem/P1117) 考虑问题等价于枚举分界点 $i$,求以 $i$ 为结尾的$AA$串个数与以 $i+1$ 为开头的 $AA$ 串的个数的积的和。 trick：考虑枚举 $A$ 的长度 $len$。每隔 $len-1$就设置一个关键点。则每个 $AA$串（长度为 $2\times len$）一定会覆盖两个关键点。考虑按相邻两个关键点的 $LCS$ 与 $LCP$ 来反推贡献。 ### [P3975 [TJOI2015] 弦论](https://www.luogu.com.cn/problem/P3975) SA做法。$t=0$显然很简单，考虑 $t=1$。 记$F(x,y)$($x\le y$) 表示 $LCP(sa_x,sa_y)$。 有 $F(x,y)\ge F(x,y+1),F(x,y)\le F(x+1,y)$。 考虑按 $rk$ 依次枚举每一个后缀，对于当前后缀 $sa_x$。显然会新增 $\sum_{i=x}^{n} F(x,i)-F(x-1,i)$ 个串的贡献。如果达到 $k$ 了，就可以二分串长然后 $check$。 ### [P4022 [CTSC2012] 熟悉的文章](https://www.luogu.com.cn/problem/P4022) 考虑二分 $L$ 然后 $dp$ $check$。显然贡献是上一个 $dp$值或一段区间。对于区间的贡献可以考虑在单调栈上二分，这样比线段树常数小很多。 ### [P4094 [HEOI2016 / TJOI2016] 字符串](https://www.luogu.com.cn/problem/P4094) 考虑二分答案 $s$（$s\le c-d+1$） 然后 $check$。显然只有 $[a,b-s+1]$ 一段的后缀才可能产生贡献。考虑每次找到对应区间关于 $rk_c$ 的前驱后继。可以线段树+正着/反着 对 $rk$ 扫描线实现。单次复杂度 $O(\log^2 \left\vert S\right\vert)$。 考虑优化，直接在线段树上维护答案，然后再线段树上二分。具体的： 关于维护答案，单点修，全局对一个数取 $\min$，维护区间最大值。 关于查询: ```cpp void qry(int u=1,int l=1,int r=n){ if(l^r)pushdown(u); if(ql<=l&&r<=qr){ if(val[u]>=qr-r){ flag=1; if(l==r)return cmax(ans,min(val[u],qr-l+1)),void(); if(val[ls]>=qr-mid)return qry(ls,l,mid); cmax(ans,val[ls]);qry(rs,mid+1,r); } else cmax(ans,val[u]); return ; } if(!flag&&ql<=mid)qry(ls,l,mid); if(!flag&&mid<qr)qry(rs,mid+1,r); } ``` 考虑 ```if(ql<=l&&r<=qr)```中最多只会向一侧递归下去。所以复杂度 $O(\left\vert S\right\vert\log \left\vert S\right\vert)$（这里的 $\left\vert S\right\vert$ 表示所有字符串的总长度）。 ### [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770) 来自询问串本身的贡献是简单的，直接查在 $rk$ 上的后继对应的后缀的 $LCP$ 即可。来自去年命名串的贡献与上一题本质相同。
正在渲染内容...
点赞
0
收藏
0
