分析
我们发现两个栈可以看作一个数组,而栈顶则是将这个数组拆成两个栈的分割点。
于是每次移动就变成了分割点的移动,每次移动时都统计下目的分割点和当前分割点之间的物品数目即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
int d[],n,n1,n2;
struct node {
int x,id;
}a[];
inline bool cmp(const node x,const node y){
return x.x>y.x;
}
inline int lb(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)d[x]+=k,x+=lb(x);}
inline int q(int x){int res=;while(x)res+=d[x],x-=lb(x);return res;}
signed main(){
int i,j,k,p,Ans=;
scanf("%d%d",&n1,&n2);
n=n1+n2;
p=n1;
for(i=n1;i>;i--)scanf("%d",&a[i].x);
for(i=n1+;i<=n;i++)scanf("%d",&a[i].x);
for(i=;i<=n;i++)a[i].id=i,add(i,);
sort(a+,a+n+,cmp);
for(i=;i<=n;i++){
if(a[i].id>p){
Ans+=q(a[i].id-)-q(p);
p=a[i].id-;
add(a[i].id,-);
}else {
Ans+=q(p)-q(a[i].id);
p=a[i].id;
add(a[i].id,-);
}
}
cout<<Ans;
return ;
}