线段树合并

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)$ 满足：
• • $1.$ $a$ $b$ $c$ 三点互不相同
  • $2.$ $a$ 和 $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 三班不一般