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

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

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

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

————————

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.