关于二次分块这么一个奇奇怪怪的东西(About such a strange thing as secondary partition)

自己口胡了一个数据结构题:

维护排列 \(s\),支持如下操作:

查询 \(s_l,s_{l+1},\cdots,s_r\) 内大于等于 \(a\) 且小于等于 \(b\) 的第 \(k\) 小数;
交换 \(s_x\) 和 \(s_y\) 的值。

维护排列 \(s\),支持如下操作:

  • 查询 \(s_l,s_{l+1},\cdots,s_r\) 内大于等于 \(a\) 且小于等于 \(b\) 的第 \(k\) 小数;
  • 交换 \(s_x\) 和 \(s_y\) 的值。

然后口胡了一下做法。

首先考虑没有修改操作的情况。考虑对值域分块,块长为 \(\sqrt n\)。维护 \(sum_{i,j}\) 表示 \(s_1\) 到 \(s_j\) 有多少个数落在第 \(i\) 块中。

那么显然预处理部分是可以 \(O(n\sqrt n)\) 搞的。

然后考虑查询。从 \(a\) 所在的块到 \(b\) 所在的块扫描一遍,每次通过 \(sum\) 求出 \(s_l\) 到 \(s_r\) 内有多少个数落在此块内,并累加到计数器 \(cnt\) 中。一旦 \(cnt\ge k\),就说明答案在当前块中,直接退出,然后再扫描一遍当前块,就把答案搞出来了。

接下来考虑修改操作。考虑将一个操作拆解为在位置 \(x\) 上删除 \(s_x\),添加 \(s_y\),在位置 \(y\) 上删除 \(s_y\),添加 \(s_x\) 这四个小操作。对于第一个小操作,设 \(s_x\) 所在的块为 \(p\),那么需要将 \(sum_{p,x},sum_{p,x+1},\cdots,sum_{p,n}\) 全部减 \(1\)。剩下的三个同理。这个东西需要在 \(O(\sqrt n)\) 的时间以内解决,否则无法保证复杂度。

而进行查询操作时,将要 \(O(\sqrt n)\) 次使用 \(sum\) 的值。因此每次获取 \(sum\) 的时间只能为 \(O(1)\)。

考虑再用一个数据结构来维护 \(sum\) 数组。这个数据结构需要满足如下条件:

  • \(O(\sqrt n)\) 以内的区间加
  • \(O(1)\) 的单点查询

那么已经呼之欲出了:序列分块。

综上所述,可以在用 \(sum\) 数组维护值域分块以支持查询操作的同时,用序列分块来维护 \(sum\) 以支持修改操作。

这样就做到了总的 \(O(n\sqrt n)\) 的时间复杂度。

空间复杂度也为 \(O(n\sqrt n)\)。

在网上查了一下并没有发现类似的东西。于是我给这个东西取名叫做二次分块。

————————

I blurted out a data structure question:

Maintain < strong > arrangement < / strong > \ (s \), and support the following operations:
Query the decimal number \ (K \) greater than or equal to \ (a \) and less than or equal to \ (B \) in \ (s_l, s_{L + 1}, \ cdots, s_r \);
Swap the values of \ (s_x \) and \ (s_y \).

Maintain < strong > arrangement < / strong > \ (s \), and support the following operations:

  • Query the decimal number \ (K \) greater than or equal to \ (a \) and less than or equal to \ (B \) in \ (s_l, s_{L + 1}, \ cdots, s_r \);
  • Swap the values of \ (s_x \) and \ (s_y \).

Then he blurted out his practice.

First, consider the case where there is no modification operation. Consider dividing the range into blocks. The block length is \ (\ sqrt n \). Maintenance \ (sum {I, J} \) indicates how many numbers from \ (s _1 \) to \ (s _j \) fall in the \ (I \) block.

Obviously, the preprocessing part can be \ (O (n \ sqrt n) \).

Then consider the query. Scan from the block where \ (a \) is located to the block where \ (B \) is located. Each time, find out how many numbers from \ (s_l \) to \ (s_r \) fall in this block through \ (sum \), and add them to the counter \ (CNT \). Once \ (CNT \ Ge K \), it means that the answer is in the current block. Exit directly, and then scan the current block again to get the answer.

Next, consider modifying the operation. Consider disassembling an operation into four small operations: deleting \ (s_x \), adding \ (s_y \), deleting \ (s_y \) and adding \ (s_x \) on position \ (Y \). For the first small operation, set the block where \ (s_x \) is located as \ (P \), then you need to subtract \ (sum {P, X}, sum {P, x + 1}, \ cdots, sum {P, n} \) by \ (1 \). The remaining three are the same. This problem needs to be solved within \ (O (\ sqrt n) \), otherwise the complexity cannot be guaranteed.

When querying, the value of \ (sum \) will be used \ (O (\ sqrt n) \) times. Therefore, the time to get \ (sum \) each time can only be \ (O (1) \).

Consider using a data structure to maintain the \ (sum \) array. This data structure needs to meet the following conditions:

  • \(O (\ sqrt n) \) plus
  • \Single point query for (O (1) \)

Then it’s ready to come out: sequence blocking.

To sum up, you can use the \ (sum \) array to maintain the value range block to support the query operation, and the sequence block to maintain \ (sum \) to support the modification operation.

In this way, the total \ (O (n \ sqrt n) \) time complexity is achieved.

The space complexity is also \ (O (n \ sqrt n) \).

I checked the Internet and didn’t find anything similar. So I named this thing secondary partition.