对题目的疑问

P2801 教主的魔法

time_keeper @ 2024-09-26 12:47:37

  • 此题能否只使用可持久化线段树解决。

  • 能不能用树状数组套权值线段树解决。

求问。

by UYHW @ 2024-11-25 20:04:48

@time_keeper

不能。不能。

by PointerMaster_3F @ 2024-12-30 13:09:27

@time_keeper 我认为可以

@UYHW 求证伪

by PointerMaster_3F @ 2024-12-30 13:11:21

我认为树状数组套主席树可以, 或者说带修主席树可以

by UYHW @ 2024-12-31 19:28:36

@PointerMaster_3F https://www.luogu.com.cn/article/dbpszuj1 当然这是依赖于目前没人会 O(n^2\log n) 矩乘的，如果你会的话你可以发篇论文

by PointerMaster_3F @ 2024-12-31 22:35:45

@UYHW 我觉得既然单点修的主席树可以用树状数组套主席树, 那区间修区间查树状数组套主席树, 是不是可以做这题

by UYHW @ 2025-01-01 08:47:07

@PointerMaster_3F 本题贡献不能快速算吧，单点修和区间修不是简单的换个能区间修的 ds 就完事了的，比如 SP1716 和 P5693

|