天降之物

link\color{deeppink}link

1 x y 将所有 xx 变为 yy

2 x y 找到满足 ai=x,aj=ya_i=x,a_j=y(i,j)(i,j),求 ij\lvert i-j\rvert 的最小值。

考虑分块。

对于每一个块,求出其中每一个值 xx,求出其最左/右边的位置;

对于每一个值对 (x,y)(x=y)(x,y)(x\not= y) 求出他们在这个块中的答案。

还要对每个块离散化一下,否则空间是 O(n2)O(n^2) 的。

修改的时候所有块跑一遍,有以下情况:

  • xx

跳过。

  • yy

交换一下 xxyy 的离散值即可。

  • x,yx,y

暴力重构。还是考虑这种情况相当于删掉一个值,最多执行 n\sqrt n 次,总复杂度是 O(nn)O(n\sqrt n) 的。

查询时就是维护一下当前最后的 x,yx,y 位置,用块中最前的位置来减即可。

时空复杂度都是 O(nn)O(n\sqrt n)注意这个做法很难过,。。。。。您需要高超的卡常技巧