https://www.lydsy.com/JudgeOnline/problem.php?id=3192

水题,注意开longlong。

把两个栈口对口连上,然后每次记录当前的栈口在哪两个元素之间,按照元素大小顺序依次找要被删掉的数的位置,之后就分类讨论即可。

注意记录一下哪些位置的数被删掉了就好,树状数组维护即可。

#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int x,y;
}b[N];
int n,m,a[N],tr[N];
inline bool cmp(node a,node b){
return a.x>b.x;
}
inline int lowbit(int t){return t&-t;}
inline void add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;
}
inline int ask(int x){
int res=;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
int main(){
n=read(),m=read();
for(int i=n;i>=;i--){
a[i]=b[i].x=read();
b[i].y=i;
}
for(int i=n+;i<=n+m;i++){
a[i]=b[i].x=read();
b[i].y=i;
}
int l=n;ll ans=;n+=m;
sort(b+,b+n+,cmp);
for(int i=;i<=n;i++){
int t=b[i].y;
if(t<=l){
ans+=l-t-ask(l)+ask(t-);
}else{
ans+=t-l-ask(t)+ask(l)-;
}
l=t-;
add(t,);
}
printf("%lld\n",ans);
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

04-20 12:35