MnZn 求助 $O(n\sqrt{n}\log n)$ 分块

User_leo @ 2023-07-05 09:34:16

by 5k_sync_closer @ 2023-07-05 09:38:07

@leo20220722 这份代码的复杂度是 O(nm) 的，因为 vector 插入删除的复杂度与其操作位置到尾部的距离成线性

by User_leo @ 2023-07-05 09:38:30

@5k_sync_closer what???!!!!!!

by 5k_sync_closer @ 2023-07-05 09:40:13

@leo20220722 瓶颈在修改时对散块的处理，遍历散块内 O(\sqrt n) 个点时，对每个点做一次 vector 上 O(\sqrt n) 的插入删除，这样一次散块处理是 O(n) 的

by 5k_sync_closer @ 2023-07-05 09:41:02

@leo20220722 不过可以类似 P5356 [Ynoi2017] 由乃打扑克 那样的归并处理散块，不需要做单点修改

by User_leo @ 2023-07-05 09:46:06

@5k_sync_closer 我被同学常数吊打了怎么办......(同样做法)

by Auto_Accepted @ 2023-07-05 09:46:25

@leo20220722 写大分块写的

by 5k_sync_closer @ 2023-07-05 09:46:43

@xuyiluo2 这是大分块？

by 5k_sync_closer @ 2023-07-05 09:46:55

@leo20220722 can can need 同学的

by Auto_Accepted @ 2023-07-05 09:48:47

@5k_sync_closer 我说我常数吊打lz是因为大分块写多了（没错，我就是那个同学

by 5k_sync_closer @ 2023-07-05 09:50:26

@xuyiluo2 草这么猛的吗，我一道大分块不会（