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

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

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

@5k_sync_closer 主要是天降之物，我序列分块太卡常了

by User_leo @ 2023-07-05 09:51:42

@5k_sync_closer 他云南蘑菇吃多了

by Auto_Accepted @ 2023-07-05 09:52:35

@5k_sync_closer 还有五彩斑斓的世界

by Auto_Accepted @ 2023-07-05 09:53:53

@5k_sync_closer 也就会三道，但卡常卡吐了

by 5k_sync_closer @ 2023-07-05 10:01:08

@leo20220722 设块长为 B，你这个做法复杂度是单次修改 O(B^2+\dfrac nB)，查询 O(B+\dfrac nB\log B)，平衡一下 B 取两三百最好

by 5k_sync_closer @ 2023-07-05 10:01:44

@leo20220722 取 250 能稳定 90 分

by 5k_sync_closer @ 2023-07-05 10:03:53

@leo20220722 实测块长 350 最好，但是还是 90 分

by ダ月 @ 2023-07-05 10:03:56

@leo20220722

1.可以手动调整块长

2.手写 vector

by User_leo @ 2023-07-05 10:08:14

@ダ月 手写......

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

@5k_sync_closer 我要不换个写法......