记录编号	413845	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013][HZOI 2016]删除物品	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.115 s
提交时间	2017-06-12 19:23:22	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define sc(a) scanf("%d",&a)
#define for1(a,b,i) for(int i=a;i<=b;i++)
const int M=100000+10;
int n,m,js,ans;
int c[M];
struct DATE{
    int bh,val;
}date[M];
inline int read(){
       int x=0,f=1;char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
       while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
       return x*f;
}
inline bool cmp(DATE a,DATE b){return a.val>b.val;}
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int num){
       while(x<=n+m){
         c[x]+=num;
         x+=lowbit(x);
       }
}
inline int gsum(int x){
       int s=0;
       while(x>0){
         s+=c[x];
         x-=lowbit(x);
       }
       return s;
} 
int main(){
    freopen("hzoi_remove.in","r",stdin);
    freopen("hzoi_remove.out","w",stdout);
    n=read();m=read();
    for(int i=n;i>=1;i--){
       date[++js].bh=i;
       date[js].val=read();
       change(js,1);
    }
    for1(1,m,i){
       date[++js].bh=i+n;
       date[js].val=read();
       change(js,1);
    }
    sort(date+1,date+js+1,cmp);
    if(date[1].bh>n)
      ans+=date[1].bh-n-1;
    else
      ans+=n-date[1].bh;
    change(date[1].bh,-1);
    for1(2,js,i){
       int a=date[i].bh,b=date[i-1].bh;
       //cout<<"bh"<<a<<" "<<b<<endl;
       if(a>b){
         ans+=(gsum(a)-gsum(b-1)-1);
         //cout<<gsum(a)-gsum(b-1)-1<<endl;
         change(a,-1);
       }
       else{
         ans+=(gsum(b)-gsum(a-1)-1);
         //cout<<gsum(b)-gsum(a-1)-1<<endl;
         change(a,-1);
       }
    }
    printf("%d",ans);
    //while(1);
    return 0;
}