双堆专题

[THUPC 2024 初赛] 二进制 (树状数组单点删除+单点查询)(双堆模拟set)

题解 题目本身不难想 首先注意到所有查询的序列长度都是小于logn级别的 我们可以枚举序列长度len,然后用类似滑动窗口的方法,一次性预处理出每种字串的所有出现位置,也就是开N个set去维护所有的位置。预处理会进行O(logn)轮,每次需要O(n*logn)的时间复杂度初始化set并计算位置。总共复杂度O(nlog^2n),看一下时间限制6s,感觉可以过23333。 删除操作可

[THUPC 2024 初赛] 二进制 (树状数组单点删除+单点查询)(双堆模拟set)

题解 题目本身不难想 首先注意到所有查询的序列长度都是小于logn级别的 我们可以枚举序列长度len,然后用类似滑动窗口的方法,一次性预处理出每种字串的所有出现位置,也就是开N个set去维护所有的位置。预处理会进行O(logn)轮,每次需要O(n*logn)的时间复杂度初始化set并计算位置。总共复杂度O(nlog^2n),看一下时间限制6s,感觉可以过23333。 删除操作可