1 x y
将所有 变为
2 x y
找到满足 的 ,求 的最小值。
考虑分块。
对于每一个块,求出其中每一个值 ,求出其最左/右边的位置;
对于每一个值对 求出他们在这个块中的答案。
还要对每个块离散化一下,否则空间是 的。
修改的时候所有块跑一遍,有以下情况:
- 无
跳过。
- 无
交换一下 和 的离散值即可。
- 有
暴力重构。还是考虑这种情况相当于删掉一个值,最多执行 次,总复杂度是 的。
查询时就是维护一下当前最后的 位置,用块中最前的位置来减即可。
时空复杂度都是 。注意这个做法很难过,。。。。。您需要高超的卡常技巧