神秘数据结构题

WorldMachine @ 2024-11-07 15:17:10

by bsdsdb @ 2024-11-07 15:24:24

@Pentiment 维护所有>=x的数的位置，修改就变成了加入/删除，动态统计答案，O(qlogn)

by WorldMachine @ 2024-11-07 15:27:43

@0x28202e202e29 thx

by WorldMachine @ 2024-11-07 15:28:00

@0x28202e202e29 但 x 是每次给定的欸

by ran_qwq @ 2024-11-07 15:33:29

目前想到莫队，一维x，一维时间，O(n\sqrt n)

by ran_qwq @ 2024-11-07 15:33:46

带个log

by Miss_SGT @ 2024-11-07 15:59:01

有一个暴力线段树树套堆的 log 方做法

by forest114514 @ 2024-11-07 16:27:41

@Pentiment 允许离线的话可以操作分块，然后块内按 x 排序，将序列变成 01 序列做。可以通过一定的方法做到只有 O(qB) 次 0\to 1 的操作，序列按 len 分块，维护块内 1 的左右位置，修改的时候只用考虑相邻两个块的答案变化，容易 O(1) 做，可以做到 O(n\sqrt q)。

by WorldMachine @ 2024-11-07 16:31:50

@forest114514 orz

by forest114514 @ 2024-11-07 17:05:42

@Pentiment 好像有强制在线的做法，对 len 根号分治。

在 len\leq B 的时候考虑按 len 分一个一级块，若干 len 的块拼成 O(\sqrt n) 的二级块，一个二级块只有 O(\sqrt n) 种 01 序列。因为只用维护每个 01 序列的答案和左右 0 段的长度，可以 O(\sqrt n) 实现修改；查询的话要每个段内二分得到对应的 01 段类型，可以分散层叠做到单次 O(\sqrt n)。

by WorldMachine @ 2024-11-07 17:07:02

@forest114514 这个太酷了