CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/10/03--2020/10/09 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

==== 专题 ====

==== 比赛 ====

==== 题目 ====

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:线段树分治]]（更新）

[[..:jxm2001:左偏树|左偏树/可并堆]]（更新）

[[..:jxm2001:重构树]]

==== 比赛 ====

[[..:jxm2001:contest:2020牛客国庆集训派对]]

==== 题目 ====

===== 王赵安 =====

==== 专题 ====

[[..:lgwza:回文树|回文树]]

[[..:lgwza:序列自动机|序列自动机]]
==== 比赛 ====

==== 题目 ====

===== 本周推荐 =====

==== 姜一凡 ====

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/P3261|洛谷p3261]]

=== 标签 ===

左偏树

=== 题意 ===

给定一棵以 $1$ 为根的树，每个点拥有属性 $(h_i,a_i,v_i)$。同时给定 $m$ 个士兵，每个士兵初始时在 $s_i$ 号点，且拥有 $c_i$ 点生命。 

当士兵 $i$ 处在点 $j$ 时，如果 $c_i\lt h_j$，则该士兵在该点死亡。

否则该士兵生命产生变化。具体得，如果 $a_i=0$ 则士兵生命增加 $v_i$，如果 $a_i=1$ 则士兵生命乘以 $v_i$。

如果士兵未死亡，则士兵通过当前结点且继续前往该结点的父节点。

询问每个结点死亡的士兵数和每个士兵最终通过的结点数。数据保证士兵任意时刻生命值不爆 $\text{long long}$ 且如果 $a_i=1$ 则 $v_i\gt 0$。

=== 题解 ===

考虑 $\text{dfs}$ 遍历城市，左偏树合并子节点士兵信息，每次弹出堆顶所有 $c\lt h$ 的结点，同时更新答案。

对于修改操作，类似线段树懒标记处理即可。由于 $a_i=1$ 时保证 $v_i\gt 0$，所有结点的相对大小不改变，所有懒标记处理可以保证正确性。

合并操作总复杂度 $(n\log m)$，弹出操作总复杂度 $O(m\log m)$，修改操作总时间复杂度 $O(n)$。于是总时间复杂度 $O((n+m)\log m)$。

=== 评价 ===

左偏树好题。

==== 王赵安 ====
CVBB ACM Team

用户工具

站点工具

页面工具
