首页 > 题解 > luogu1110 [ZJOI2007]报表统计

luogu1110 [ZJOI2007]报表统计

上午有有人提起了这个题,翻了一下发现还没A。。。

当时写得一个set骗分,bzojAC但是luogu的模拟CCF的老爷机没A。

代码在这

竟然T了!我要卡常!

那就重新想想吧。

题目要求维护一坨数,能够随时插入,查询相邻的数的最小差值,查询任意两数间的最小差值。

第二问比较好写,由于set被卡了,于是写了个treap。。每次插入后查询一下前驱和后继更新一下答案。然后这个答案显然是递减的,所以数列中有相同的数之后就不用理了。

然而第一问就没法用treap做了。。把原数列存在map[]里面。

假设是在原数列第pos个元素后插入一个数x,那么x的右边的那个数就是map[pos+1](如果$pos < n$的话)

x左边的那个数其实就是本来第pos个元素后面插了一坨数的最后一个,用last[i]表示当前(插入x之前)第i个元素后面插进去的一坨数的最后一个数的大小。

所以把x插进去后,原先的差值abs(last[pos]-map[pos+1])不存在了,新增了两个差值为abs(last[pos]-x)和abs(x-map[pos+1])

用优先队列(堆)维护下差值就好了。。。。。

具体姿势:

对于新增的差值abs(last[pos]-x),它是不会被新增的数影响的。。然而abs(x-map[pos+1])可能因为之后在x后面插进去新的数而不存在。。。

判断这个差值存不存在就看x是不是所在元素的最后一次插入的数。每次查询的时候先把队头(小根堆顶)那些不存在的差值弹掉就行了。

事实证明这样写主要时间复杂度是在treap上= =。。。优先队列的速度比treap高明到不知道哪里去了。。treap的速度又比spaly高明到不知道哪里去了。。。

发现大部分的时间都是在treap建树的时候。。。所以直接把数列排序后递归建树。。。(参见文艺平衡树。)

我有特殊的卡常技巧23333


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×