这个系列用于记录学习省选知识点的过程中做题的笔记，系列名就是这样 因为省选的知识点真的是又多又杂，题单也是又难又长，不排除同时多个题单一起开工的情况，所以如果这一部分完成了就是
[done]的前缀，做中就是[working]可能会跳过一些 lxl 题
线段树
LG P2023
线段树 2 板子题，一眼秒。取模比较沙币，直接上 __int128 比较舒适。
LG P4513
这是一个经典套路题了，线段树维护区间最大子段和，对于每个 $node$ 维护：
- $lmax$：从左端点向右延伸的最大子段和
- $rmax$：从右端点向右延伸的最大子段和
- $sum$：区间和
注意一下 seg.query() 的区间。
LG P1471
跟着 @DPair 推一下公示，转化一下 Pushdown。
LG P6327
维护少见的区间信息有常见的两个套路化思考方法：
- 拆分成维护好的信息
- 直接维护，考虑修改对其的影响
这里是和角公式：
$$ \begin{aligned} \sin(x + v) = \sin x \cos v + \cos x \sin v \\ \cos(x + v) = \cos x \cos v - \sin x \sin v \\ \end{aligned} $$运用法 2，我们使用和角公式来通过维护区间 $\sin, \cos$ 和来 $O(1)$ 地下传标记。
LG P3792
数学题都被 Ynoi 除名了
线段树维护区间 $\min, \max$ 区间和区间平方和。
通过 $\max, \min$ 算出如果这是个连续段，那么其平方和应该是多少。
因为是 lxl 题所以同时维护区间最大最小值，区间和，区间平方和和区间立方和。
给两组公式：
$$ \begin{aligned} \sum_{i = 1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6} \\ \sum_{i = 1}^{n} i^3 = \left( \frac{n(n + 1)}{2} \right)^2 \\ \end{aligned} $$LG P5278
码起来很恶心。
考虑组成等差数列的要求：
- $seq_{\max} - seq_{\min} = d(r - l)$
- $\forall i, j, k \in [1, n], i \neq j \neq k \to \gcd(|a_i - a_j|, |a_j - a_k|) = d$
- $\forall i, j \in [1, n] \to a_i \neq a_j$
使用线段树 + map + set 维护最大值，最小值，前驱最大值，区间左端点值，区间右端点值，差的 $\gcd$。
都说数据水我还是写了一天，服了。
LG P6617
定义一个数的前驱为这个位置之前第一个与这个位置相加和为 $w$ 的位置，没有就是 $0$，答案为检查区间内所有数的前驱是否 $\geq l$。
转化！如果这个数的前驱比它前面第一个与它相同的位置要小，直接将其设为 $0$ 是正确的。
然后这样修改之后新变化的位置最多有 $5$ 个：现位置、现位置原后面第一个与其相同的位置、现位置原后面第一个相加得 $w$ 的位置、现位置修改后第一个与其相同的位置，现位置修改后第一个与其相加得 $w$ 的位置
又恨又爱的 set 维护一下位置，上线段树修改。
LG P5069
注意到操作位置 $x$ 时，必有 $a_x \gt a_{x - 1} \And a_x \geq a_{x - 1}$。所以找到满足的 $x$ 后 $x - 1, x + 1$ 显然都不会被操作，只能一直把 $x$ 减到 $0$，所以答案就是 $\sum a_x$。
把序列抽离出来变成连续的不降序列和上升序列交替出现。对于每一小段不降序列或者上升序列，其最大值必定会被操作到。最大值在端点外时，会带走相邻的一个，两个两个地带走最大值，操作位置的 奇偶性 不变，对于奇数和偶数位置分别维护一颗 Fenwick 记录和。对于每小段子序列记录下极值点，用 std::set 维护。
修改时只考虑修改极值点，首先把 $x - 1, x, x + 1$ 从位置中删除，加入新极值点时，新的极值点只可能在修改的位置的 $x - 1, x, x + 1$ 中出现。
良心 Ynoi 不卡常，$O(n \log n)$ 过。
LG P4139
其实是下一道题的前置知识要求。
对于任意的 $b \geq \varphi(p)$，我们有：
$$ a^b \equiv a^{b \bmod \varphi(p) + \varphi(p)} (\bmod p) $$对于任意的 $b \lt \varphi(p)$，则有：
$$ a^b \equiv a^{b \bmod \varphi(p)} (\bmod p) $$这个题里显然套第一个公式递归往下做就可以了。
LG P3747
第一想法是：这尼玛能 SegTree 维护？
然后想到了扩展欧拉定理，然后可以发现这种脑瘫处理多半是有特殊性质的，参见 花神游历各国。
这道题同理，我们套上扩展欧啦定理，暴力修改到 $\varphi(\varphi(\varphi(\varphi(\dots \varphi(\varphi(p)))))) = 1$ 之后不管了，因为此时已经变成了 $c^{c^{c^{c^{{\dots}^c}}}}$，与 $a_i$ 无关，每个点最多会被修改 $2 \log p$ 次，每次修改最多需要 $\log$ 次的递归，还有一只 $\log$ 的快速幂，用光速幂搞掉一只 $\log$，整道题目就可以在 $O(m \log^2 p)$ 的时间复杂度下解决。
一句话：扩欧+花神游历各国+光速幂。·
以后看到这种特殊的维护信息不要慌，想一想相关的数学知识或者发掘一下特殊性质，特别是与极差有关或者类似的暴力修改。
LG P1486
pb_ds 拯救世界
显然是平衡树，但是我们平衡树并不能做到区间加减，所以考虑一个常见 Trick：维护全局工资下界，记录当前工资下界和原始值的差，每次查询减去这个差。
又有一个常用的平衡树 Trick：存放 std::pair<int, int> 而不是 int 用于防止重复元素（维护 metadata 太麻烦了吧）。
LG P4036
限制了询问次数，注意到离谱的 std::string 可过。
LG P5482
树状数组可做。对于这种题还是太过迟钝了，没有想到值域上建树的第一想法。
corner case 比较多要讨论起来小麻烦，但是按照 lxl 的 PPT 来看的话确实这道题的本质并不难：
- $ax + b \gt c \Longleftrightarrow \dfrac{c - b}{a}$
- 值域上树状数组
- 插入时取整，查询时前缀和
LG P3586
明显的贪心。
记录两棵 Fenwick，第一棵记录离散化后 $1$ 到 $i$ 中数字的出现个数，第二棵树状数组记录离散化前 $1$ 到 $i$ 数字出现的值的和。离线询问：
- 对于操作 1：若之前的数是正数，第一棵 $- 1$，第二棵 $- ori$；若之后的数是正数，第一棵 $+ 1$，第二棵 $+ ori$（$ori$ 表示原来的数）
- 对于操作 2：将 $\gt s$ 的个数求出来，再比较 $c$ 和大于 $s$ 的个数乘上 $c$ 与剩余数字之和，若前者大则输出 $\rm NIE$，否则输出 $\rm TAK$
LG P3987
前面还有几道比较傻的平衡树，主要是调试恶心就懒得写了，从这个 lxl 题继续记录。
势能分析。什么平衡树？不懂啊，我们考虑用线段树来做这个问题。
显然操作 1 无法直接维护，那么我们考虑进行一个暴力。
维护 $n$ 个 std::vector $e$，其中对于 $e_i$ 记录所有能被 $i$ 整除的数的编号，对编号进行二分，每次遇到除法操作就在 $e_x$ 里找到符合条件的区间 $[l, r]$ 然后暴力修改，我们考虑记录这个操作的次数到 $t[]$ 里，如果操作的次数非常多，每操作一次就将不是 $x$ 的倍数的数删掉，这样子暴力会快一点。
传统艺能，我们发现 $5e5$ 大约 $19, 20$ 次左右去除以 $2$ 就到 $1$ 了，特判一下 $1$。
跑得飞快。
有个强化卡常版 LG P5610，知识点学完之后会板刷 YNOI 的，不急。
LG P3224
平衡树启发式合并，当然也可以写线段树合并。
然后我们发现就这两个操作可以上 pb_ds，还要个并查集。然后就写完了。
pb_ds 大法好。
LG P3201
容易想到链表维护，暴力修改。但是暴力复杂度是错的，考虑启发式合并来维护信息。
LG P4197
类似永无乡的套路，离线下询问按照 $x$ 升序排序，这样子我们就成功去掉了 $h_i \leq x$ 这一限制。
然后用并查集维护从 $v_i$ 开始能够经过的所有山峰，用权值线段树维护区间第 $k$ 大，合并连通块时也要合并线段树。
不知道为什么好恶心啊这个题码起来，调了半天。
LG P5586 & P5350
恶心，太恶心了，写吐了。
其实除了区间复制之外就是普通的可持久化平衡树，但是由于这个空间问题我们需要进行一个定期重构。
平衡树什么的写起来最讨厌了。