P9994 [Ynoi Easy Round 2024] TEST_132
根号分治。
考虑修改操作。如果修改的x数量大于阙值B，那么打上操作次数标记，否则直接各自修改对应的\(y_i\)答案。
查询时对于一个y,记录下所有使得xi数量大于B且yi=y的i，这一些贡献是没有加上的。
显然xi的数量<=n/B,对于每一个这样的xi快速幂暴力加上贡献时间复杂度可以承受。
当然这种做法是可以优化的，也就是去掉快速幂的复杂度达到完全线性。
具体来说1e9+7的原根是5，可以预处理5的光速幂，查询O(1)计算答案。
CF603E Pastoral Oddities
首先有一个结论：每个点的度数都是奇数等价于图中只存在大小为偶数的连通块
必要性：一条边使得两个点度数加1，度数之和一定是偶数，每个点的度数又都是奇数，就只能是点数为偶
充分性：对于每一个偶数大小的连通块，随便拿出它的一颗生成树，从底向上跑一遍这个算法：
如果这个节点儿子连上来的边数为偶数，就连上他与父亲的边，反之则不然。
我们发现，这样的构造可以满足除了根的所有节点的限制。
然而因为这个连通块内除根外其他节点的数量是奇数，而这些点的度数都是奇数，而包括根的总度数是偶数，所以根的度数自然也是奇数
现在开始考虑最小化最大边权的限制。
先不考虑动态加边，根据上面的思路，我们要找的是一颗生成树，那就是求最小生成树，Kruskal一下（从小到大加边）就行了。
可以得到静态版本的解法：
把边按权值排序，用并查集维护奇联通块的个数，一直加边直到满足条件
考虑怎么把这个做法推广到动态：
发现只有加边操作，没有删边。所以有一个显然的结论：一条边如果加边之前没有入选，那么加边以后一定也不会被选中。也就是说，每一条边有一个影响范围
影响范围+时间轴->线段树分治
考虑求一条边的影响区间。首先出现时间是知道的。考虑在线段树分治的过程中，每访问到一个叶子，必定需要后移Kruskal的指针，将新的边纳入答案直到合法，那么这个时间就是这条边影响范围的结束位置。
P8512 [Ynoi Easy Round 2021] TEST_152
自己第一次想的时候有一抽象想法：
把操作序列分块，每一块预处理出一起操作的结果。显然后操作的会覆盖前操作的。那么从后往前扫，把覆盖过的起点直接指向终点后面，前面的操作如果覆盖到一样的地方直接跳过去。
不知道时间复杂度是否是O(nsqrt(n))，理论可行的话也一定很难写（这种题目就不可能好写）
正解：
把询问离线，按照 r 排序，然后我们每次询问的时候。
我们可以开一个 set 来维护 c 序列。
set 中每个节点有一个三元组 (l,r,v)(l,r,v)，表示cl...cr都为 v。
每次询问的时候，我们维护执行 \(1 \sim r\) 操作后 c 序列，每个节点同时存储是哪次操作产生的节点。然后我们询问 \([l,r]\) 的时候，就是所有产生时的操作编号 \(\geq l\) 的节点的权值和。
这个我们用树状数组维护即可。
P4458 [BJOI2018] 链上二次求和
考虑把起点固定为1,计算一个数的贡献。
对于一个固定的区间k，考虑一个位置i的贡献。
不难发现，对于一个位置，有三种限制：
- 1.距离1的长度i
- 2.距离n的长度n-i+1
- 3.k的大小
也就是三者取最小值
不难得出计算公式：
三个式子取最小值显然是不好处理的，考虑能不能先去掉一个。
对于i和n-i+1两者的大小关系，其实i靠近起点就是i小，靠近终点就是n-i+1小。
于是我们可以把计算公式从中间分成两半，只考虑i或n-i+1与k的大小关系就行了
先考虑左半边：
\[\sum_{i=1}^{n/2}a_i\sum_{k=l}^{r}min(i,k) \]
不难分析出结果，右半边同理。
后面的操作还没搞懂