线段树合并
CF600E Lomsat gelral
给定一个大小为
n 并且以1 为根的树。对于树上的结点i 有一个颜色c_i 现在对于树上的每一个结点
i ，输出以i 为根的子树出现最多的颜色的编号，如果有多个颜色出现次数均为最大，输出它们的编号和。1\leq n \leq 10^5$，$1\leq c_i \leq n
-
用线段树合并求出每一个点的子树信息。
-
以颜色
c_i 作为下标建立线段树。叶子结点存对应的颜色出现次数，非叶子结点存最大出现次数mx和编号和sumID -
然后就是线段树合并，对于叶子结点，累加即可。对于非叶子节点
x ，先把其的左右儿子和y 的左右儿子对应合并，然后考虑push_up这个过程。 -
代码
CF570D Tree Requests
给定一个以
1 为根的树。树上的每一个点i 都有一个小写字母c_i 有
q 次询问，每次询问给定两个参数a 和b ，表示询问a 子树内深度为b 的结点的c_i 是否能重新排列成为一个回文串。1\leq n \leq 5 \times 10^5$，$1\leq q \leq 5\times 10^5
-
线段树合并，以深度
dep为下标建立线段树。 -
由于
c_i 只有26 中，而且只需要考虑每一个字母出现次数的奇偶性，因此状压即可。 -
由于只询问某一个深度，因此线段树上只需要维护叶子结点的信息，查询某一个深度的信息时在线段树上二分即可。
-
代码
P3899 [湖南集训] 更为厉害
给定一个大小为
n 并且以1 为根的树。有
q 次询问，每次询问给定两个参数a 和k ，表示询问有多少个点对(b , c) 满足：
3.$ $a$ 和 $b$ 距离为不超过 $k 1\leq n \leq 3\times 10^5
-
若
b 为a 的祖先节点，则只需要令c 为a 的子树节点即可。贡献为\min \{ \text{dep}[a] - 1 , k \} \times (\text{siz}[b] - 1) -
若
b 为a 的子树节点，则需要查询a 子树内深度\text{dep}[x] 在\text{dep}[a] + 1 \sim \text{dep}[a] + k 范围\text{siz}[x] - 1 之和。 -
以
\text{dep} 为下标建立线段树，线段树合并即可。 -
注意
upd函数要写一个if(!u) u = ++ idx -
代码
P8907 [USACO22DEC] Making Friends P
给定
n 头奶牛，初始有m 对朋友关系现在奶牛以
1 \sim n 的顺序离开。每当一头奶牛i 离开时，它所有的朋友都会互相建立朋友关系。问
n 头奶牛离开之后，新增了多少对朋友关系。1\leq n \leq 2\times 10^5$，$1\leq m \leq 2 \times 10^5
-
考虑一种延迟的操作，每次找到与
i 相邻并且编号最小的点p ，然后让p 和i 的其余朋友v_1, v_2,...,v_k 连边。即把i 集合内除了p 的所有元素扔到p 集合里面。 -
发现每次取出
i 时都能保证i 集合是当前i 的所有朋友结点，累加答案即可。 -
感觉理解的不好
-
代码
P9400 「DBOI」Round 1 三班不一般
整体 dp