[ZJOI2007]报表统计

题目链接

题解

又是一道题一晚上系列(数据结构一生之敌)

调了很久的原因其实是写错了一个变量,其实还是很简单的

这里用的平衡树是Treap

你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存
用vector就很舒服

然后对于第三个操作,其实只要每次进入平衡树的元素查找下前驱后继与它本身作差取最小值即可(这里的前驱后继是非严格的)

对于第二个操作,每次插入一个元素,总会创造两个差值关系并且减去一个差值关系
我们可以用两个小根堆分别维护产生的差值和删去的差值,每次询问时,不断弹出顶端相同元素后,第一个堆顶就是答案了

这种做法还是有点慢的(最慢1500ms,开了O2 790ms),如果当年省选不开O2的话有点悬

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注