题目链接：CF或者洛谷想了很久，然后想起做过的一道题：秃子酋长，一开始以为差不多，结果写着写着就发现不对劲了。最后写出了个神仙回滚莫队解法，感觉很妙，记录下。进入神仙分析时刻首先，我们来考虑一个事实，加上一个数以后，如果能找到它的前后驱，那么可以立马更新最优解，这个也即是瓶颈点。

压位trie好厉害。显然加一个数很好维护，删一个数有点不好做，考虑回滚莫队。用平衡树维护数的集合，每次插入之前用前驱/后继与插入数的差更新一下答案，可以\(O(n\sqrt{n}\logn)\)，会Timelimitexceededontest7or8。看上去我们已经优化到极限了，怎么办呢？显然莫队的\(n\sqrt{

Preface在会压位Trie的前提下，本题最好想的做法应该是压位Trie+回滚莫队，可是竟然没人写这个做法的题解？Solution我们先转化题意：设\(a_i\)在\([l,r]\)中的前驱后继

分块。\(f[i][j]\)：\(i\)一直到第\(i\)所在块\(x\)尾端，对\(x+1\simj\)块造成贡献/\(i\)一直到\(i\)所在块\(x\)开头，对\(j\simx-1\)块造成贡献。\(mn[i][j