```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
struct Data
{
int a, t, res;
}q[N], w[N];
int tr[N], pos[N];
LL ans[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
int i = mid, j = r;
while (i >= l && j > mid)
if (q[i].a > q[j].a) add(q[i].t, 1), i -- ;
else q[j].res += query(q[j].t - 1), j -- ;
while (j > mid) q[j].res += query(q[j].t - 1), j -- ;
for (int k = i + 1; k <= mid; k ++ ) add(q[k].t, -1);
j = l, i = mid + 1;
while (j <= mid && i <= r)
if (q[i].a < q[j].a) add(q[i].t, 1), i ++ ;
else q[j].res += query(q[j].t - 1), j ++ ;
while (j <= mid) q[j].res += query(q[j].t - 1), j ++ ;
for (int k = mid + 1; k < i; k ++ ) add(q[k].t, -1);
i = l, j = mid + 1;
int k = 0;
while (i <= mid && j <= r)
if (q[i].a <= q[j].a) w[k ++ ] = q[i ++ ];
else w[k ++ ] = q[j ++ ];
while (i <= mid) w[k ++ ] = q[i ++ ];
while (j <= r) w[k ++ ] = q[j ++ ];
for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &q[i].a);
pos[q[i].a] = i;
}
for (int i = 0, j = n; i < m; i ++ )
{
int a;
scanf("%d", &a);
q[pos[a]].t = j -- ;
pos[a] = -1;
}
for (int i = 1, j = n - m; i <= n; i ++ )
if (pos[i] != -1)
q[pos[i]].t = j -- ;
merge_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) ans[q[i].t] = q[i].res;
for (int i = 2; i <= n; i ++ ) ans[i] += ans[i - 1];
for (int i = 0, j = n; i < m; i ++, j -- ) printf("%lld\n", ans[j]);
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/599411/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```
by ByGones @ 2023-06-27 08:13:24
就是分治之前，不是要先按第一关键字排序吗
by ByGones @ 2023-06-27 08:18:30
初始时已经按时间排好序了啊。
by james1BadCreeper @ 2023-06-27 08:19:07
@[ByGones](/user/209848) 这道题第一关键字是时间，所以你读入时已经排好序了
by 六楼溜刘 @ 2023-06-27 08:39:44
谢谢
by ByGones @ 2023-06-27 17:32:21