ZigZagK

Never give up fighting!

[树状数组]BZOJ3192(JLOI2013)【删除物品】题解

题目概述

一共有两堆物品,分别有 \(n\) 个和 \(m\) 个。所有物品都是一样的,但是它们有不同的优先级。只能够移动某堆中位于顶端的物品,你可以把任意一堆中位于顶端的物品移动到另外一堆的顶端。若此物品是当前所有物品中优先级最高的,可以直接将之删除而不用移动。求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

解题报告

因为只有两堆,所以移动操作是固定的,可以用两个Splay来维护,这道题就解决了……

然而写两个要求排名的Splay简直就是有毒,我们可以再探究一下移动的性质:

1  2    2  7X  5X 4
4  7    1  3      1
5  3 -> 4    ->   2 -> ...
        5         7X
                  3

我们发现如果不把删除的物品移出物品堆,那么实际上只有一个分开两堆的指针在移动:

5  4  1  2  7  3 -> 5  4  1  2  7X 3 -> 5X 4  1  2  7  3 -> ...
      ^                      ^          ^

那么原问题就变成一个区间查询问题,注意一下新指针在左和右两种情况就行了。

示例程序

被绕晕了……这么点代码竟然写了很久QAQ……

点赞

发表评论

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