1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define ll long long
using namespace std;

const int MAXN = 110000;

namespace fast_io{
    //...
}using namespace fast_io;

struct Q{
    bool w;
    int id,b,c;
    // id -> 加入时间 b -> 加入的位置 c -> 这个数的大小
    Q(int x,int y,int z):id(x),b(y),c(z){}
    Q(){}
    bool operator < (Q w)const{//用于排序
        if(id!=w.id) 
            return id < w.id;
        if(b!=w.b)
            return b < w.b;
        return c < w.c;
    }
}q[MAXN];

int n,m;
int num[MAXN],pos[MAXN],del[MAXN];
ll ans[MAXN];
// num -> 原数组
// pos -> 值对应的位置
// del -> 删除第 pos 个数的序顺 

namespace BIT{
    ll sumn[MAXN];
    int lowbit(int x){
        return x & (-x);
    }
    void add(int x,int d){
        while(x <= n) sumn[x] += d,x += lowbit(x);
    }
    ll query(int x){
        ll ans = 0;
        while(x >= 1) ans += sumn[x],x -= lowbit(x);
        return ans;
    }
}

void init(){
    read(n),read(m);
    for(int i = 1;i<=n;i++){
        read(num[i]);
        pos[num[i]] = i;
    }
    int tmp; 
    for(int i = 1;i<=m;i++){
        read(tmp);
        del[pos[tmp]] = i;
    }
}

int l,r,tot,tmp[MAXN];

inline bool judge(int x,int y){
    //判断归并顺序函数 这里因为不重复，可以不写其他维判定
    return q[x].b < q[y].b;
}


void CDQ(int *t,int num){
    if(num == 1) return;
    int mid = num/2;
    CDQ(t,mid),CDQ(t+mid,num-mid);//分治解决问题
    //进行归并
    for(l=0,r=mid,tot=0;tot < num;tot++){
        if((r==num)||(l<mid && judge(t[l],t[r])))//这一行的条件易错
            q[t[l]].w = 0,tmp[tot] = t[l++];
        else
            q[t[r]].w = 1,tmp[tot] = t[r++];
    }
    for(int i = 0;i<num;i++) t[i] = tmp[i];

    //统计id(time)比其小 b(pos)比其小 c(val)比其大的数的个数
    for(int i = 0;i<num;i++)
        if(!q[t[i]].w) BIT::add(q[t[i]].c,1);
        else ans[q[t[i]].id] += BIT::query(n)-BIT::query(q[t[i]].c);
    for(int i = 0;i<num;i++)
        if(!q[t[i]].w) BIT::add(q[t[i]].c,-1);
    //统计id(time)比其小 b(pos)比其大 c(val)比其小的数的个数
    for(int i = num-1;i>=0;--i)
        if(!q[t[i]].w) BIT::add(q[t[i]].c,1);
        else ans[q[t[i]].id] += BIT::query(q[t[i]].c-1);
    for(int i = num-1;i>=0;--i)
        if(!q[t[i]].w) BIT::add(q[t[i]].c,-1);
}

void solve(){
    int nowcnt = 0;
    static int tt[MAXN];
    for(int i = 1;i<=n;i++){
        //遍历每个pos 
        if(del[i] == 0) q[i] = Q(1,i,num[i]);
        else q[i] = Q(m-del[i]+2,i,num[i]);
    }
    sort(q+1,q+1+n);
    for(int i = 1;i<=n;i++)
        tt[i] = i;
    CDQ(tt+1,n);
    // 前缀和统计答案
    for(int i = 1;i<=m+1;i++)
        ans[i] += ans[i-1];
    for(int i = m+1;i>1;--i)
        print(ans[i]),print('\n');
}

int main(){
    init();
    solve();
    flush();
    return 0;
}