Eva

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

箱子再分配问题需要解决如下问题：

 （1）一共有N个物品，堆成M堆。

 （2）所有物品都是一样的，但是它们有不同的优先级。

 （3）你只能够移动某堆中位于顶端的物品。

 （4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。

（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

 （6）只是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：

         不会有两个物品有着相同的优先级，且M=2

Input

第一行是包含两个整数N1,N2分别表示两堆物品的个数。

接下来有N1行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级，数字越大，优先级越高。

再接下来的N2行按照同样的格式给出了第二堆物品的优先级。

Output 

对于每个数据，请输出一个整数，即最小移动步数。

Sample Input

3 3
1
4
5
2
7
3

Sample Output

6

HINT

1<=N1+N2<=100000

/**************************************************************

    Problem: 3192

    User: ictsing

    Language: C++

    Result: Accepted

    Time:292 ms

    Memory:2464 kb

****************************************************************/

 

//n个物品，分成2堆，每个物品有优先级

//每次只能移动堆顶的物品，若该物品是所有的优先级最高的，则会被删除

/*

毫无思路的题QAQ

模拟肯定可以做，所以考虑用数据结构来维护这个东西

经过发现可知，

如果把两个堆的堆顶对起来，或者放在一起可以用树状数组加快模拟过程

然后就没了...

****

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int mt = 100000+5;

int bit[mt],n,m;

struct ha{

   int x,pos;

}a[mt];

typedef long long ll;

bool cmp(ha a,ha b)

{

    return a.x>b.x;

}

void add(int x,int v)

{

    for(;x<=n;x+=(x&-x)) bit[x]+=v;

}

int sum(int x)

{

    int ans=0;

    for(;x>0;x-=(x&-x)) ans+=bit[x];

    return ans;

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++)

        a[i].x=read(),a[i].pos=n-i+1;

    int last=n;

    for(int i=1;i<=m;i++)

        n++,a[n].x=read(),a[n].pos=n;

    sort(a+1,a+n+1,cmp);

    ll res=0;

    for(int i=1;i<=n;i++) add(i,1);

    for(int i=1;i<=n;i++)

    {

        int now=a[i].pos,tmp=0;

        if(now>=last) tmp=sum(now-1)-sum(last);

        else tmp=sum(last)-sum(now);

        if(tmp>0) res+=tmp;

        add(now,-1),last=now;

    }

    printf("%lld",res);

    return 0;

}