显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=100010;
struct A{
int w,p;
bool operator<(const A &a)const{return a.w<w;}
}a[maxn];
void add(int,int);
int query(int);
int n,m,c[maxn],tmp,ans=0;
int main(){
#define MINE
#ifdef MINE
freopen("hzoi_remove.in","r",stdin);
freopen("hzoi_remove.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=n;i;i--){
scanf("%d",&a[i].w);
a[i].p=i;
}
for(int i=n+1;i<=n+m;i++){
scanf("%d",&a[i].w);
a[i].p=i;
}
tmp=n;
n+=m;
for(int i=1;i<=n;i++)add(i,1);
//for(int i=1;i<=n;i++)printf("%d ",a[i].w);printf("\n");
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i].p<tmp){
ans+=query(tmp)-query(a[i].p);
//printf("i=%d p=%d tmp=%d ans=%d\n",i,a[i].p,tmp,ans);
tmp=a[i].p;
}
else if(a[i].p==tmp)tmp=a[i].p;
else{
ans+=query(a[i].p-1)-query(tmp);
//printf("i=%d p=%d tmp=%d ans=%d\n",i,a[i].p,tmp,ans);
tmp=a[i].p-1;
}
add(a[i].p,-1);
}
printf("%d",ans);
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return 0;
}
void add(int x,int d){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
/*
3 3
1 4 5
2 7 3
*/
/*
5 5
5 10 7 6 4
1 3 2 8 9
*/
AntiLeaf