主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
CF600E Lomsat gelral
最后更新于 2025-08-28 09:12:53
作者
2huk
分类
题解
题解
CF600E
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
线段树合并。 考虑合并两颗线段树，设它们分别以 $root_x$ 和 $root_y$ 为根。我们递归合并这两颗线段树上的每个节点： ```cpp 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$ 为空则合并等于没有。否则左右分别递归，并信息上传。 动态开点保证了复杂度。 对于本题，我们在每个节点开一颗线段树，然后将所有儿子合并到父亲即可。
正在渲染内容...
点赞
0
收藏
0
