高级数据结构常见套路

元旦快乐！

题单

线段树分裂与合并 ​

动态开点线段树 ​

堆式线段树采用点 $i$ 的左儿子为 $2\times i$，右儿子为 $2\times i+1$ 的结构，很容易根据父亲找到儿子。但是对于节点较少的线段树，这样存储可能会浪费大量空间。

例如：

• 如果一棵线段树只有一条右链，即每个节点是父亲的右儿子，右链的叶子上存储了信息，那么这个节点的编号是 $O(n)$ 级别的，然而树上有用节点只有 $O(\log n)$ 个。

• 如果维护一棵值域是 $10^{9}$ 的权值线段树，使用堆式建树有 $O(V)$ 个节点，显然不可接受。然而每一次操作只会访问到 $O(\log V)$ 个节点，在 $q$ 次操作下，有用节点实际上只有 $O(q\log v)$ 个。

上述两种情况说明，在堆式建树可能会产生无效节点。

不再认为点 $i$ 的左儿子为 $2\times i$，右儿子为 $2\times i+1$，而是记录线段树上每一个节点的左右儿子的下标。初始根的左右儿子下标为 $0$。

当访问到一个标号为 $0$ 的节点时，新建一个节点，将信息储存在这个节点，处理完之后返回这个新标号即可。

比如说单点修改可以这么写（将 p 的值改为 v）：

int chg(int p, int v, int id, int l, int r) {
  if (!id) id = ++cnt;
  if (l == r) {
    // update information
    return id;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) ls[id] = chg(p, v, ls[id], l, mid);
  else rs[id] = chg(p, v, rs[id], mid + 1, r);
  // merge ls[id] and rs[id]
  return id;
}

线段树合并 ​

现在有两棵动态开点线段树，希望将两棵线段树的信息合并。

对于只有一棵线段树有信息的位置，将有信息的节点返回即可。对于两棵树均有信息的节点，递归合并两棵子树，再将两棵子树的信息合并。

假设有 $T$ 个位置两棵树都有值，这样复杂度是 $O(\text{T})$ 的

int merge(int u, int v, int l, int r) {
  if (!u || !v) return u | v;
  if (l == r) {
    // merge information u and v to u
    return u;
  }
  int mid = (l + r) >> 1;
  ls[u] = merge(ls[u], ls[v], l, mid);
  rs[u] = merge(rs[u], rs[v], mid + 1, r);
  // merge ls[u] and rs[u]
  return u;
}

P4556 雨天的尾巴 ​

Link

给定一棵 $n$ 个节点的树，有 $m$ 次操作，每一次操作在 $(x,y)$ 的路径上放置一个类型为 $z$ 的物品。求每一个位置最多放置的物品类型。

$1\le n,m,z_i\le 10^{5}$