P15652：一个询问的不是前后缀的做法

· · 题解

让我们找一个排列把所有的 (l,r) 询问打出来：

先从 B 性质开始吧：9 7 5 3 1 0 2 4 6 8

跑出来是这样的

0 0 0 0 0 2 4 6 8 10 
0 0 0 0 0 2 4 6 8 9 
0 0 0 0 0 2 4 6 7 7 
0 0 0 0 0 2 4 5 5 5 
0 0 0 0 0 2 3 3 3 3 
0 0 0 0 0 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

注意到其实就是从右上角每次向左或向下一步一步走到这个主对角线上的 1。

好让我们再换一个排列 9 7 2 6 1 0 3 5 4 8

0 0 0 0 0 3  4  4  8  10x 
0 0 0 0 0 3  4  4  8x 9x 
0 0 0 0 0 3x 4x 4x 7x 7 
0 0 0 0 0 2x 2 2 2 2 
0 0 0 0 0 2x 2 2 2 2 
0 0 0 0 0 1x 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

注意到依然是这么走的，路线已经在图上标出来了。进一步注意到，我们会往较大的那一侧走。并且较小的那一侧会继承。

如果你注意到了这些，问题就解决了：维护当前区间 (L,R) 向左向下的两个值 Lv=\mathrm{mex}(L,R-1),Rv=\mathrm{mex}(L+1,R)。不妨假设 Lv 较大，则我们令 R\gets R-1，然后重新求 Lv 而 Rv 不变。

相信大家都能够通过这个过程还原排列。

至此问题解决，并且奇妙地避过所有挂分点！

补一些证明：

然后好像没什么可以证的了？

upd：注意到，如果你不想证明，你不需要知道 \mathrm{mex} 是什么。