Description
对于序列 \(a\)，它的逆序对数定义为集合
\[\{(i,j)| i<j \and a_i > a_j \} \]中的元素个数。
现在给出 \(1\sim n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Solution
发现 \(a_{i}\) 很大，肯定先离散化后处理。
可以先求出所有的逆序对，在每次删除数之后就减去这个数对逆序对的贡献。
我们再给每个要删掉的数一个删除时间，若这个数没有被删除，那么就把删除时间设置为 INF。
贡献如何计算？
-
位置在这个数前面，数值比该数大，且删除时间比它晚的数。
-
位置在这个数后面，数值比该数小，且删除时间比它晚的数。
我们要找的都是删除时间比它晚的数，否则即使能产生逆序对，也因为更早被删除而计入更早那个数的贡献，不能重复计数。
现在这个问题就转化成了静态三维数点（三位偏序）的问题，且可以离线，考虑用 CDQ 分治做。
先按照时间的从晚到早的顺序排序，去掉了一维，然后不断递归，分成左右区间，每次递归完成后计算左右区间跨区间的贡献即可。
注意这里要计算两次贡献，每一次贡献计算完毕后应当清空树状数组。
Code
// by youyou2007 in 2022.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
/*
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
*/
const int N = 100005;
struct node{
int t, pos, val;
long long ans;
}a[N];
int n, m, tree[N], del[N], id[N];
bool cmp1(node x, node y)//外层排序，按照时间排序
{
if(x.t != y.t) return x.t > y.t;
return x.pos < y.pos;
}
bool cmp2(node x, node y)//内层排序，按照位置排序
{
return x.pos < y.pos;
}
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int y)
{
while(x <= n)
{
tree[x] += y;
x += lowbit(x);
}
}
int query(int x)
{
int res = 0;
while(x > 0)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}
void CDQ(int l, int r)
{
if(l == r) return;
int mid = (l + r) / 2;
CDQ(l, mid);
CDQ(mid + 1, r);
sort(a + l, a + mid + 1, cmp2);
sort(a + mid + 1, a + r + 1, cmp2);
int j = l;
for(int i = mid + 1; i <= r; i++)//计算比该数大且位置更靠前的数的个数
{
while(j <= mid && a[i].pos >= a[j].pos)
{
add(a[j].val, 1);
j++;
}
a[i].ans += query(n) - query(a[i].val);
}
for(int i = l; i <= j - 1; i++)//清空树状数组
{
add(a[i].val, -1);
}
j = mid;
for(int i = r; i >= mid + 1; i--)//计算比该数小且位置更靠后的数的个数
{
while(j >= l && a[i].pos <= a[j].pos)
{
add(a[j].val, 1);
j--;
}
a[i].ans += query(a[i].val - 1);
}
for(int i = mid; i >= j + 1; i--)
{
add(a[i].val, -1);
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i].val);
a[i].pos = i;
a[i].t = n + 4;//若该数未被删除过，则随便定一个比较大的值
id[a[i].val] = i;//记录下每个数原来的位置
}
for(int i = 1; i <= m; i++)
{
scanf("%d", &del[i]);
a[id[del[i]]].t = i;
}
long long now = 0;
for(int i = 1; i <= n; i++)//先利用一次树状数组处理出初始逆序对数量
{
now += query(n) - query(a[i].val);
add(a[i].val, 1);
}
for(int i = 1; i <= n; i++)
{
add(a[i].val, -1);
}
sort(a + 1, a + n + 1, cmp1);
CDQ(1, n);
sort(a + 1, a + n + 1, cmp2);//最后应当按照删除时间顺序再排一遍
for(int i = 1; i <= m; i++)
{
printf("%lld\n", now);
now -= a[id[del[i]]].ans;//注意题目要求，应当先输出再减
}
return 0;
}