CF600E Lomsat gelral

2huk · 2024-08-13 21:45:51 · 题解

线段树合并。

考虑合并两颗线段树，设它们分别以 root_x 和 root_y 为根。我们递归合并这两颗线段树上的每个节点：

void merge(int &x, int y, int l, int r) {
  if (!x) x = y;
  else if (!y) return;
  else if (l == r) {
    tr[x].v.first += tr[y].v.first;
    tr[x].v.second = l;
  }
  else {
    int mid = l + r >> 1;
    merge(tr[x].l, tr[y].l, l, mid);
    merge(tr[x].r, tr[y].r, mid + 1, r);
    pushup(x);
  }
}void merge(int &x, int y, int l, int r) {
  if (!x) x = y;
  else if (!y) return;
  else if (l == r) {
    tr[x].v.first += tr[y].v.first;
    tr[x].v.second = l;
  }
  else {
    int mid = l + r >> 1;
    merge(tr[x].l, tr[y].l, l, mid);
    merge(tr[x].r, tr[y].r, mid + 1, r);
    pushup(x);
  }
}

merge(root[x], root[y], 1, N);

表示我们要把节点 y 合并到 x 上。如果 x 为空则 x \gets y，如果 y 为空则合并等于没有。否则左右分别递归，并信息上传。

动态开点保证了复杂度。

对于本题，我们在每个节点开一颗线段树，然后将所有儿子合并到父亲即可。