记录编号	572332	评测结果	AAAAAAAAAA
题目名称	千风的诗篇	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.452 s
提交时间	2022-06-30 17:23:29	内存使用	9.36 MiB

#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(ll x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
/////////////////////////
const int N=1e5+50;
int nc,mc;
int n[N];
int _n[N];
struct M
{
    int sz;
    int p;
    int t;
    int sp;
}m[N];
ll a1[N],a2[N];//左侧大，左侧小 
ll b1[N],b2[N];//右侧大，右侧小 
ll f1[N];
ll sum;
inline int lowbit(int x){return x&(-x);}
inline ll fin(int x)
{
    ll re=0;
    for(;x;x-=lowbit(x)) re+=f1[x];
    return re;    
} 
inline void get_in(int x){for(;x<=nc;x+=lowbit(x)) f1[x]++;}
bool cmp1(M x,M y){return x.sz>y.sz;}
bool cmp2(M x,M y){return x.t<y.t;}
ll f2[N];
inline ll FIN(int x)
{
    ll re=0;
    for(;x;x-=lowbit(x)) re+=f2[x];
    return re;    
} 
inline void GET_IN(int x,int y){for(;x<=nc;x+=lowbit(x)) f2[x]+=y;}
void CDQ(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r); 
    sort(m+l,m+mid+1,cmp2),sort(m+mid+1,m+r+1,cmp2);//先后顺序排序（先-后） 
    int rs=l;
    rep(i,mid+1,r)
    {
        while(m[rs].t<m[i].t&&rs<=mid) GET_IN(m[rs++].p,1);
        m[i].sp+=FIN(m[i].p);
//        if(m[i].sz==5) cout<<"LR#:"<<l<<" "<<r<<" "<<FIN(m[i].p)<<endl;
    }
    rep(i,l,rs-1) GET_IN(m[i].p,-1);
    //
    int ls=mid+1;
    rep(i,l,mid)
    {
        while(m[ls].t<m[i].t&&ls<=r) GET_IN(m[ls++].p,1);
        m[i].sp+=(ls-mid-1-FIN(m[i].p));
//        if(m[i].sz==5) cout<<"LR#:"<<l<<" "<<r<<" "<<ls<<" "<<m[4].t<<" "<<ls-mid-1-FIN(m[i].p)<<endl;
    }
    rep(i,mid+1,ls-1) GET_IN(m[i].p,-1);
}
ll ans[N];
int main()
{
    freopen("windy.in","r",stdin);
	freopen("windy.out","w",stdout);
    nc=read(),mc=read();
    rep(i,1,nc)
    {
        n[i]=read();
        a2[i]=fin(n[i]);
        a1[i]=i-1-a2[i];
        b2[i]=n[i]-1-a2[i];
        b1[i]=nc-n[i]-a1[i];
        sum+=a1[i];
        get_in(n[i]);
        _n[n[i]]=i;
    }
//    cout<<"SUM:"<<sum<<endl;
    rep(i,1,mc) m[i].sz=read(),m[i].p=_n[m[i].sz],m[i].t=i;
    sort(m+1,m+1+mc,cmp1);//大小排序（大-小） 
    CDQ(1,mc);
    rep(i,1,mc) ans[m[i].t]=a1[m[i].p]+b2[m[i].p]-m[i].sp;
//    rep(i,1,mc) cout<<m[i].t<<":"<<m[i].sz<<" "<<a1[m[i].p]<<" "<<b2[m[i].p]<<" "<<m[i].sp<<endl;
    rep(i,1,mc) write(sum),putchar(10),sum-=ans[i];
    return 0;
}
//6 5
//5 4 6 3 1 2
//4 1 5 3 2
//A:12 8 5 3 1