首先我们考虑第一种情况怎么处理，显然我们可以给原数列的每个数开一个\(vector\)，每加一个数丢到对应的\(vector\)后面就行了。
再看第二个操作，你考虑新加一个数会有什么影响。
原来的两个\(vector\)是这样的：
新加一个数进去以后：
原来的\(|y-x|\)要删除，新增了\(|x-z|\)和\(|z-y|\)，我们直接用一个\(fhq-treap\)维护任意相邻两项的差，每次只需要删除一个，增加两个，复杂度是对的。
最后是第三个操作，考虑新加一个数组单独给所有数排序，新加入一个数先二分找到插入位置，再新增两个差值，用另一个\(fhq-treap\)维护，而且不用删掉原来的。
为什么明明插入一个数，原来两边的差值没有了却不用删除呢？
这是显然的，如果它一开始就不是最优的当然不用管，如果是最优的，中间差一个数结果也不会更劣。
总结：这题的难度在于码力
标签：P1110,一个,题解,treap,新加,vector From： https://www.cnblogs.com/wangwenhan/p/17636207.html