题解

写这个题解，是不是，约等于水帖了。

根据题意，一堆物品在一个栈里永远正序，另一个栈永远倒序，不妨把两个栈栈顶接起来，询问就是回答从刚删的位置到新删的位置间有多少没被删的物品，可以用 BIT 实现，怎么做完了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define mn(x,y) ((x<y)?(x):(y))
#define mx(x,y) ((x>y)?(x):(y))
#define ab(x) ((x<0)?(-x):(x))
#define mid (l+r>>1)
inline long long read(){
    long long x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
inline void write(long long x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[19],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
int n1,n2,a[100005],t[200005],top,o[100005];
ll ans;
inline bool cmp(int x,int y){return a[x]>a[y];}
inline void del(int x){for(;x<=n1+n2;x+=x&-x)t[x]--;}
inline int qry(int x){int res=0;for(;x;x^=x&-x)res+=t[x];return res;}
signed main(){
    n1=read(),n2=read(),top=n1;
    for(int i=n1;i>=1;--i)a[i]=read(),o[i]=i;
    for(int i=n1+1;i<=n1+n2;++i)a[i]=read(),o[i]=i;
    sort(o+1,o+n1+n2+1,cmp);
    for(int i=1;i<=n1+n2;++i)t[i]++,t[i+(i&-i)]+=t[i];
    for(int i=1;i<=n1+n2;++i){
        int t=qry(o[i]);
        ans+=t<=top?top-t:t-top-1;
        del(o[i]),top=t-1;
    }
    write(ans);
    return 0;
}