小清新 ds

线段树

我也不知道该分到哪里

GSS3 - Can you answer these queries III

经典最大子段和

维护前缀 $\max$ ，后缀 $\max$ ，和区间最大子段，区间和就好了

#2055. 「TJOI / HEOI2016」排序

首先有一个经典做法，就是二分答案，将大于 $ans$ 的值设为 $1$ ，小于 $ans$ 设为 $0$ ，这样排序就很好做了，时间复杂度 $O(n\log^2 n)$

但是其实还有 $O(n\log n)$ 的做法，就是你那权值线段树维护序列的连续有序段，每次操作相当于合并一些线段树，倒序就打一个 $tag$ 就好了，注意边界可能在一颗线段树里面，所以还需要线段树分裂，这样复杂度就是 $O(n\log n)$ 了，因为你发现你一次操作最多分裂出来两颗线段树，所以合并是 $O(n+m)$ 次

代码写一半丢了所以开摆了

CF1783G Weighed Tree Radius

首先将权值 $a_i$ 转变成向外挂一个点，边权为 $a_i$ （注意这里要挂两个，因为 $w_v(v)$ 是合法的

发现这个半径好像很不好做，~~再根据他的名字联想~~，我们可以想到求出直径，最后输出 $\lceil \frac{len}{2} \rceil$ ，至于为什么这样是对的，因为离每个点最远的点一定都是直径上的点，所以中点是半径最小的

现在问题就好做了，边权修改，直径查询，用线段树维护即可，具体来说，就是根据直径性质，两颗树合并到一块新的直径端点一定出自原来两棵树的四个直径端点中，可以合并

因为常数巨大，所以我写了 $O(1)\ LCA$ 但是 $\text{strange757}$ 实测 $O(n\log^2n)$ 可过

code （u1s1，我不知道我写的是什么

CF1192B Dynamic Diameter

线段树维护直径板子

线段树维护 $dfn$ 序，每个点到根节点的权值用 $bit$ 维护，修改 $(u,v)$ 时重新算一下所有包含 $u$ 的和包含 $u+sz_u-1$ 的就行了

code

CF1149C Tree Generator™

$($ 表示往下做一步，所以深度 $+1$ ，同理 $)$ 导致深度减 $1$ ，所以设 $($ 为 $1$ ， $)$ 为 $-1$

然后就有一个很牛逼的东西了，我们可以把一条长度为 $x+y$ 路径 $u,v$ 看成 $u$ 先走 $x$ 个 $-1$ 走到 $lca(u,v)$ ，然后走 $y$ 个 $1$ 走到 $y$ ，发现这个玩意可以直接转到括号序上，因为我要是在递归 $u$ 所在子树和递归 $v$ 所在子树中间递归了其他子树，这是肯定会回溯上来的，所以算上这一段也不会对答案有影响，现在就是等于把题意转化成了：给定一个 $1,-1$ 序列，单点修改，查询 $\max\limits_{1 \le l \le r \le n}sum_{k+1,r}-sum_{l,k},k\in[l-1,r]$ ，其中 $sum_{l,r}$ 表示 $[l,r]$ 这一段的权值和，这个玩意就可以用线段树维护了

具体来说，我们设 $ans$ 为要求的答案，现在枚举 $k$ 在 $[l,mid]$ 还是在 $(mid,r]$ ，下面说的全局 $ans$ 最大值就是 $l,r$ 和区间 $l,r$ 相同，前缀/后缀 $ans$ 最大值就是固定前缀/后缀是 $l/r$ 的 $ans$ 最大值

当 $k$ 在 $[l,mid]$ 时需要一个右区间的前缀权值 $\max$ 拼在后面，左区间需要一个后缀 $ans$ 最大值， $k$ 在 $(mid,r]$ 时同理左区间后缀权值 $\min$ ，右区间前缀 $ans$ 最大值，考虑前缀/后缀 $ans$ 最大值要怎么求，这个就是需要全局 $ans$ 最大值，然后前缀权值 $\max$ 还需要一个区间权值和，将这些都维护上就好了

code

线段树合并

~~我发现这玩意是纯傻逼，啥都过不去~~

#3046. 「ZJOI2019」语言

我们对于每个点求出所有他能到的点，不难发现这肯定是一个连通块，现在考虑怎么快速计算这个连通块内有多少点，因为原图是树，所以这个连通块一定是树，考虑什么点会跟当前点 $u$ 联通，肯定是经过了经过 $u$ 的链，所以我们将所有经过 $u$ 的链进行链覆盖，这个可以树上差分，而树上差分有一个很经典的东西，就是将 $p_1,p_2,p_3,…,p_n$ 两两相连构成的连通块覆盖等于将 $p$ 按 $dfn$ 序排序，对于 $p_i$ 加一，对于 $lca(p_i,p_i+1)$ 和 $lca(p_1,p_2,p_3,…,p_n)$ 减一，这个题我们也可以这样，但是这样复杂度依然很高，继续优化

发现我对于每一个点都算很亏，发现答案其实就是加一的点的 $dep$ 减去减一的点的 $dep$ ，这样虽然复杂度没变，但是这个显然比刚才那个好优化

发现你子树里面的很多信息当前点也可以用，考虑线段树合并，线段树区间 $l,r$ 维护 $dfn$ 序在 $l,r$ 时所有关键点和 $1$ 号点能覆盖的点的数量，其中关键点就是每条链的链首链尾，对于一条链 $u,v$ ，我们让他在 $u,v$ 时都加入关键点 $u,v$ 在 $lca(u,v)$ 的时候在都减回来，用上面说的那个 $dep$ 求方法维护一下就可以了

code

#2537. 「PKUWC2018」Minimax

不是很难

首先先想一下暴力 $dp$ ，设 $f_{u,j}$ 表示现在在节点 $u$ ，权值是 $v_j$ 的概率，因为只有最多两个子节点，所以很好转移，时间复杂度 $O(n^3)$ ，可以优化，但是不重要

现在考虑用线段树合并优化这个东西，在合并区间 $l,r$ 的时候维护左/右儿子权值是 $[v_1,v_{l-1}]$ ， $[v_{l+1},v_r]$ 的概率，直接线段树合并就可以了

code

#3340. 「NOI2020」命运

好强的 $dp$ 状态

考虑 $dp$ ，设 $f_{u,j}$ 表示我现在在 $u$ 节点，目前不满足要求的属于 $Q$ 人生经历在第 $j$ 层结束，特殊的， $j=0$ 时表示没有属于 $Q$ 的不满足要求的人生经历

转移就很好转移了，假设我现在在点 $u$ ，我要把 $v$ 的 $dp$ 转移过来，有柿子：

$f_{u,j}=\sum\limits_{i=0}^{dep_u} f_{u,j}\times f_{v,i}+\sum\limits_{i=0}^{j}f_{u,j}\times f_{v,i}+\sum\limits_{i=0}^{j-1}f_{v,j}\times f_{u,i}$ ，第一个 $\sum$ 是这条边为 $0$ ，后面两个 $\sum$ 为 $1$

这个玩意拿前缀和优化一下就是 $O(n^2)$ 的了，能拿到 $40pts$ ，考虑优化，~~因为刚刚做了 Minimax~~ 我们知道线段树合并是可以搞前后缀 $dp$ 的，所以直接线段树合并就可以了

code

李超树

P4097 [HEOI2013] Segment

李超树区间插线段板子

code 自认为写的还是能看的

P4655 [CEOI2017] Building Bridges

李超树优化 $dp$

这玩意做斜率优化 $dp$ 都不用动脑子的

先搞一个 $dp$ ，设 $f_i$ 表示我现在不拆第 $i$ 根柱子将桥从 $1$ 架到 $i$ 的最小花费，不难发现转移是枚举上一个没拆的主子 $f_i=\min\limits_{j=1}^{i-1}\{f_j+sum_{i-1}-sum_j+(h_i-h_j)^2\}$ ，好棒！

考虑优化，这是一个标准的斜率优化柿子，化简一下有

$f_i=\min\limits_{j=1}^{i-1}\{f_j+sum_{i-1}-sum_j+{h_i}^2+{h_j}^2-2h_ih_j\}$

$f_i=\min\limits_{j=1}^{i-1}\{f_j-sum_j+{h_j}^2-2h_ih_j\}+sum_{i-1}+{h_i}^2$

外面的常数都不用考虑，只看里面

将每一个 $f_j$ 看成斜率是 $-2h_j$ 截距是 $f_j-sum_j+{h_j}^2$ 现在就等于有一堆直线，我们要查询位置 $h_i$ 的最小值，直接上李超树就行了

CF932F Escape Through Leaf

李超树线段树合并

设 $f_u$ 表示从 $u$ 走到叶子节点的最小代价，转移就是 $f_u=\min\limits_{v}\{f_v+a_u\times b_v\}$ ，这玩意就是一个标准的斜率优化，直接李超树合并就行了

至于怎么李超树合并，其实就是暴力，差不多就是把一颗李超树里面的所有直线全部插进另一颗里面，具体可以看代码，但是注意这个时间复杂度其实是 $O(n \log n)$ 的，因为线段树的深度是 $O(\log n)$ 的，是所以每条线段最多向下走 $O(\log n)$ 次，所以复杂度是 $O(n\log n)$

code

兔队线段树

就是如果前缀会影响当前节点的情况的时候可以考虑用这个东西

P4198 楼房重建

下面说的楼的高度均除以 $i$

对于线段树上每个点维护只考虑当前区间 $[l,r]$ 的所有楼，能看见几栋楼，现在考虑怎么更新，我们定义一个函数 $calc$ 表示考虑 $[l,r]$ ， $[1,l)$ 中楼的最高高度为 $pre$ ，这段区间内有多少楼能看见，设 $mid$ 为当前区间中点， $mx$ 表示区间最大值，假设 $[l,mid]$ 的 $mx$ 小于 $pre$ ，那么左区间一个都不可能在当前区间答案里面，直接递归右区间就可以了，假设 $[l,mid]$ 的 $mx$ 大于 $pre$ ，那么右区间是不受 $pre$ 影响的，只用递归左区间，这样 $calc$ 的时间复杂度是 $O(\log n)$ 的，不难发现有了这个就很容易算线段树上维护的东西了

注意到我要是想知道 $(mid,r]$ 受到 $[l,mid]$ 影响时的答案是需要减的，但是可能其他题维护的东西没有可减性，所以可以线段树每个区间维护在左区间影响下右区间的答案，这样就不用减法了

code

P9130 [USACO23FEB] Hungry Cow P

还是考虑兔队线段树，每个节点维护 $cnt,sum,to$ 表示当前区间有几天有干草，右区间有干草的日期编号和和给后面的区间贡献多少干草，还是搞一个 $calc$ 函数，要是左区间加上前面贡献过来的已经填满了就直接等差数列加起来就可以了，然后递归右区间，要是没加满就说明这个不会贡献到右区间，只用重新算左区间

code 代码非常比较抽象

CF671E Organizing a Race

segbeats

等我闲的没事的时候再写吧

主席树

#2016. 「SCOI2016」美味

看见异或直接上 $trie$ ，然后不会做， $trie$ 好像根本不能平移 👈🤣

但是主席树可以干这个玩意 😎

贪心从高位考虑到低位看一看这一位异或后能不能是 $1$ ，因为前面位的 $01$ 已经确定，所以这一位是 $1$ 的位置肯定连续，减 $x_i$ 后也一定连续，在权值线段树上查就行了，区间交给主席树

时间复杂度 $O(n\log^2 n)$

code

关于线段树上的一些进阶操作 - command_block 的博客 - 洛谷博客 (luogu.com.cn)

cdq 分治

一个我非常讨厌的算法，虽然我也不知道为什么

平衡树

根号

分块

#6282. 数列分块入门 6 - 题目 - LibreOJ

操作：单点插入，单点询问

也没啥，数据随机就直接插就行了，数据要是不随机就定期重构一下，~~块长我也不知道设多少合适~~

code

#6284. 数列分块入门 8 - 题目 - LibreOJ

发现一次修改最多把两个块内数全相同的改成不是全相同的所以块内数不同的只有 $O(n)$ 个，直接做就好了

~~不如线段树~~

#6285. 数列分块入门 9 - 题目 - LibreOJ

挺强的

早就忘了 🐸

$O(n\sqrt{n \log n})$ ：等我想起来再写

$O(n\sqrt n)$ ：

要是询问两边块编号一样直接暴力

要是不一样发现可能的众数只有 $\sqrt n$ 种：散块部分出现的数和所有整块的众数

预处理出 $A_{i,j}$ 表示第 $j$ 个数在块 $[1,i]$ 中出现次数， $B_{i,j}$ 表示块 $[i,j]$ 的众数，直接做就行了

P5356 [Ynoi2017] 由乃打扑克

其实不是很难

首先有一个一眼的方法，对于每个块维护块内数排序后的结果，修改时散块直接暴力重构，整块打标记，查询就先二分答案，然后再对于每一个块二分求出有多少数小于等于第一个二分的答案，这样散块复杂度是 $O(B\log B)$ ，整块复杂度是 $O(\frac{n}{B}\log w \log B)$ ，其中 $w$ 是值域，将 $\log w,\log B$ 视为同阶，平衡复杂度后复杂度为 $O(q\sqrt{n\log B}\log B)$ ，寄！