/*
*
* 构造三种属性,三维偏序问题用CDQ分治算法来求解,属性a是点的权值,就是1到N的数值,属性b是点的下标,属性c是点被删除的时间点,设第一个
* 删除的点的删除时间是N, 后面删除的点的删除时间依次递减(没有删除的点的删除时间从剩下的时间点中随机分即可)
*
* 假设删除时间是i的点和删除时间是j的点构成了一个逆序对(i,j), 那(j, i)也是一个逆序对,但是两个逆序对计数只能算一次,统一规定将计数累计到i
* j中偏大的那个点上,也就是较早删除的点上,定义s[i]表示是删除时间为i的点上累加的逆序对计数,在这样的一种特殊构造出的定义之下,问题所求的"删除
* 某点之前的逆序对数量"(假设这个点删除时间是i), 就是s[i] + s[i-1] + s[i-2] + ..... s[1], 就是一个前缀和,所以只需要考虑了怎么求s[i]
*
* 删除时间是i的节点可能产生两种逆序对(这里的i值就是节点中的c属性):
*
* 第一种,node(i)的值偏小, 和比其更晚删除的一个值偏大的点j配成逆序对,贡献累加到i节点上:
* node(j).a > node(i).a && node(j).b < node(i).b && node(j).c < node(i).c
*
* 第二种, node(i)的值偏大,和比其更晚删除的一个值偏小的点j配成逆序对, 贡献累加到i节点上:
* node(j).a < node(i).a && node(j).b > node(i).b && node(j).c < node(i).c
*
* (两种类型的逆序对交换角色也是没问题的,问题对称过来还是一样的)
*
* 对这两类逆序对,对每一个节点求出其所有能构造出的这两类逆序对,把贡献值在对应的位置上进行累加,所有的逆序对是不重不漏的
* 所以问题就变成了两个独立的三维偏序问题(问题中的大于符号,将原属性取相反数就可以变成小于号),分别求解,然后再做一次前缀
* 和,对于每一个询问,打印出对应的前缀和即可
*
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_FENWICK_LEN = 100005;
int sum_seg[MAX_FENWICK_LEN];
class FenwickTree {
private:
int data_len; // 存储的前缀和的长度
// 获取区间[0, end]的前缀和
int __get_sum_with_end(int end) {
int ans = 0;
while (end) {
ans += sum_seg[end];
end &= (end - 1);
}
return ans;
}
public:
FenwickTree(int n) : data_len(n) {
for (int i = 1; i <= n; i++) {
sum_seg[i] = 0;
}
}
// 获取在x的原始数值
int get_orig_val(int x) {
x += 1;
if (x < 1 || x > data_len) {
// 异常分支
return 0;
}
int ans = sum_seg[x];
int lca = x & (x-1);
x--;
while (x != lca) {
ans -= sum_seg[x];
x &= (x-1);
}
return ans;
}
// 获取区间[start, end]的前缀和
int get_sum(int start, int end) {
start++, end++;
if (! (end >= start && start >= 1 && end <= data_len)) {
// 异常分支
return 0;
}
if (start == 1) {
return __get_sum_with_end(end);
}
return __get_sum_with_end(end) - __get_sum_with_end(start - 1);
}
// x位置的原始序列数值增加delta
void add_val(int x, int delta) {
x += 1;
while (x <= data_len) {
sum_seg[x] += delta;
x += x & (-x);
}
}
};
const int MAX_NODE_NUM = 100005;
// 三元组,表示三个维度属性值
struct Node {
int a, b, c; // 三个维度的属性值
int cnt; // 原序列中数值等于(a, b, c)的节点个数
int le_num; // 对于数值等于(a, b, c)的原序列中的点X, 三维偏序小于等于X的原序节点的数量(不包括X节点自己)
bool operator < (const Node& other) const {
if (a != other.a) return a < other.a;
if (b != other.b) return b < other.b;
return c < other.c;
}
bool operator == (const Node& other) {
return a == other.a && b == other.b && c == other.c;
}
} buf[MAX_NODE_NUM], buf1[MAX_NODE_NUM], buf2[MAX_NODE_NUM], merge_buf[MAX_NODE_NUM]; // buf是输入数据的缓存,也是结果缓存,merge_buf是归并排序时候使用的额外缓存
// 分治解决[ll, rr]区间中的问题, 按照b属性进行归并排序
FenwickTree fenwick(100005 + 10);
// s[i]表示和删除时间戳是i的数值配对的逆序对数量
long long s[MAX_NODE_NUM];
void merge_sort(int ll, int rr) {
if (ll == rr) {
return;
}
int mid = (ll + rr) >> 1;
merge_sort(ll, mid);
merge_sort(mid+1, rr);
int ii = ll - 1;
int pos = -1;
for (int jj = mid + 1; jj <= rr; jj++) {
while (ii+1 <= mid && buf[ii+1].b <= buf[jj].b) {
ii += 1;
fenwick.add_val(buf[ii].c, buf[ii].cnt);
merge_buf[++pos] = buf[ii];
}
int sum_val = fenwick.get_sum(0, buf[jj].c);
s[buf[jj].c] += sum_val;
buf[jj].le_num += sum_val;
merge_buf[++pos] = buf[jj];
}
// 将树状数组还原回去
for (int i = ll; i <= ii; i++) {
fenwick.add_val(buf[i].c, -buf[i].cnt);
}
while (ii+1 <= mid) {
ii += 1;
merge_buf[++pos] = buf[ii];
}
// 子区间合并
for (int i = ll; i <= rr; i++) {
buf[i] = merge_buf[i-ll];
}
}
// n是输入的三元组数组的长度
void cdq(int n) {
sort(buf, buf + n);
merge_sort(0, n-1);
}
// 数值到下标的映射
int val2idx[MAX_NODE_NUM];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
int val;
for (int i = 0; i < n; i++) {
scanf("%d", &val);
val2idx[val] = i;
buf1[i].a = val;
buf1[i].b = i;
buf1[i].c = 0;
buf1[i].cnt = 1;
}
for (int i = 0; i < m; i++) {
scanf("%d", &val);
buf1[val2idx[val]].c = n - i;
}
int rank = n-m;
for (int i = 0; i < n; i++) {
if (buf1[i].c == 0) {
buf1[i].c = rank--;
}
}
for (int i = 0; i < n; i++) {
buf[i] = buf1[i];
buf[i].a = n+1 - buf1[i].a;
}
cdq(n);
for (int i = 0; i < n; i++) {
buf[i] = buf1[i];
buf[i].b = n+1 - buf1[i].b;
}
cdq(n);
// s求前缀和
for (int i = 1; i <= n; i++) {
s[i] += s[i-1];
}
for (int i = n; i > n-m; i--) {
printf("%lld\n", s[i]);
}
return 0;
}