主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
最后更新于 2025-08-28 09:12:22
作者
2huk
分类
题解
题解
P4556
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
路径加可以树上差分。即令 $res_{i, j}$ 表示答案中第 $i$ 个节点上 $j$ 种类的数量，$d_{i, j}$ 为其差分数组。每次操作 $(x, y, z)$ 等价于： $$ d_{x,z} \gets d_{x, z} + 1 \\ d_{y,z} \gets d_{y, z} + 1 \\ d_{lca,z} \gets d_{lca, z} - 1 \\ d_{fa_{lca},z} \gets d_{fa_{lca}, z} - 1 $$ 发现 $d_{i, 1\sim n}$ 可以用线段树维护，而最后做一次前缀和的过程为线段树合并。
正在渲染内容...
点赞
0
收藏
0
