题目概述

一共有两堆物品，分别有 $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……

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,m,a[maxn+5],c[maxn+5],pos[maxn+5];LL ans;

inline bool cmp(int A,int B) {return a[A]>a[B];}
inline void Update(int x,int tem) {for (int i=x;i<=n+m;i+=i&-i) c[i]+=tem;}
inline int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=n;i>=1;i--) scanf("%d",&a[i]),Update(i,1),pos[i]=i;
    for (int i=n+1;i<=n+m;i++) scanf("%d",&a[i]),Update(i,1),pos[i]=i;
    int lst=n;sort(pos+1,pos+1+n+m,cmp);
    for (int i=1;i<=n+m;Update(pos[i++],-1))
        if (lst<pos[i]) ans+=Sum(pos[i]-1)-Sum(lst),lst=pos[i]-1;
        else ans+=Sum(lst)-Sum(pos[i]),lst=pos[i];
    return printf("%lld\n",ans),0;
}