题解

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int pos,val,op,id;
    bool operator <(const node&xyl)const{return pos<xyl.pos;}
}a[150005];
int n,N,m,ans[50005],tree[100005],idx[100005];
void modify(int x,int d){
    for(int i=x;i<=n;i+=i&(-i))tree[i]+=d;
}
int sum(int x){
    int res=0;
    for(int i=x;i>=1;i-=i&(-i))res+=tree[i];
    return res;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq(l,mid),cdq(mid+1,r);
    for(;cnt2<=r;++cnt2){
        while(cnt1<=mid&&a[cnt1].pos<a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),++cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*(sum(n)-sum(a[cnt2].val));
    }
    for(int i=l;i<cnt1;++i)modify(a[i].val,-a[i].op);
    for(cnt1=mid,cnt2=r;cnt2>=mid+1;--cnt2){
        while(cnt1>=l&&a[cnt1].pos>a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),--cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*sum(a[cnt2].val-1);
    }
    for(int i=mid;i>cnt1;--i)modify(a[i].val,-a[i].op);
    sort(a+l,a+r+1);
}
int read(){
    int 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;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[++N]={i,read(),1,0},idx[a[N].val]=i;
    for(int i=1;i<=m;++i)a[++N].val=read(),a[N].pos=idx[a[N].val],a[N].id=i,a[N].op=-1;
    cdq(1,N);
    for(int i=1;i<m;++i)ans[i]+=ans[i-1];
    for(int i=0;i<m;++i)write(ans[i]),putchar('\n');
    return 0;
}