社区讨论

晶石后任

2025/11/12 23:09P6018[Ynoi2010] Fusion tree参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 0 条
当前快照: 1 份
快照标识符: @mhz49apy
此快照首次捕获于: 2025/11/15 01:12
此快照最后确认于: 2025/11/16 13:47

不要忘了少输入一个变量而导致 RE/WA（话说真的有人会犯这样低级的错误吗……
动态开点字典树（是这个名字吗？），tree 数组要开够空间。理论上一共 $n$ 个节点，每个节点最多贡献 $\log a_i$ 个节点，共 $n \log n$ 个节点，也就是说开 $19 \times N = 9.5 \times 10 ^ 6$ ，考虑到还有最多 $m$ 次的 $+1$ 操作，开到 20 倍 $n$ 足矣。
不要忘了类似懒标记的东西，只有单点修改允许直接在原数组改，多点一起修改的时候加在懒标记里。
不要忘了判当前操作的点（ $x$ 的父亲、祖父等）存不存在，否则你会在无效根的字典树上增减查，喜提 hack 数据 WA 的成绩。此hack数据原帖。

回复

共 0 条回复，欢迎继续交流。

正在加载回复...