题目链接：传送门

Description

对于序列A，它的逆序对数定义为满足i < j，且Ai > Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4 1 5 3 4 2 5 1 4 2

Sample Output

5 2 2 1

Solution

这道题的树套树做法

CDQ分治做法：

我们将询问离线，将删除看成倒过来加入。设每个元素位置，值，被删除时间分别为pi,vi,tip_i, v_i, t_i

那么第ii个元素被加入时，所有满足以下条件的jj都能产生贡献：

ti<tj pi<pj vi>vjt_i < t_j\ p_i<p_j\ v_i>v_j 或ti<tj pi>pj vi<vjt_i < t_j\ p_i>p_j\ v_i<v_j

那么我们只需要先以tt为关键字排序，然后cdq去掉pp这一维，用树状数组维护vv的信息即可

Code

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 100000 + 100, Maxm = 50000 + 100;

int N, M;

struct node
{
	int t, p, v, ans;
}A[Maxn];

inline int read ()
{
	char ch = getchar(); int sum, fl = 1;
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	sum = ch - '0';
	ch = getchar();
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

inline int cmp1 (node a, node b) { return a.t < b.t; }
inline int cmp2 (node a, node b) { return a.p < b.p; }
inline int cmp3 (node a, node b) { return a.v < b.v; }

namespace BIT
{
#define lowbit(x) (x & (-x))
	int Sum[Maxn << 1];
	inline void add (int x, int v) { while (x <= N) { Sum[x] += v; x += lowbit(x); } }
	inline int query (int x) { int ans = 0; while (x) { ans += Sum[x]; x -= lowbit(x); } return ans;}
}

inline void Solve (int l, int r)
{
	if (l == r)
		return ;
	int mid = (l + r) >> 1;
	Solve (l, mid), Solve (mid + 1, r);

	int pos = r;
	for (int i = mid; i >= l; --i)
	{
		while (pos > mid && A[pos].p > A[i].p)
			BIT :: add(A[pos].v, 1), --pos;
		A[i].ans += BIT :: query(A[i].v - 1);
	}
	for (int i = r; i > pos; --i) BIT :: add(A[i].v, -1);

	pos = mid + 1;
	for (int i = l; i <= mid; ++i)
	{
		while (pos <= r && A[i].p > A[pos].p)
			BIT :: add(A[pos].v, 1), ++pos;
		A[i].ans += BIT :: query(N) - BIT :: query(A[i].v);
	}
	for (int i = mid + 1; i < pos; ++i) BIT :: add(A[i].v, -1);
	sort(A + l, A + r + 1, cmp2);
}

int Ans[Maxn];

main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	scanf("%lld%lld", &N, &M);
	for (int i = 1; i <= N; ++i) A[i].v = read(), A[i].p = i;
	sort(A + 1, A + N + 1, cmp3);
	for (int i = 1; i <= M; ++i)
	{
		int x = read();
		A[x].t = i;
	}
	for (int i = 1; i <= N; ++i)
		if (!A[i].t) A[i].t = M + 1;
	sort(A + 1, A + N + 1, cmp1);
	Solve (1, N);
	sort(A + 1, A + N + 1, cmp1);
	int ans = 0;
	for (int i = N; i >= 1; --i)
	{
		ans += A[i].ans;
		Ans[A[i].t] = ans;
	}
	for (int i = 1; i <= M; ++i) printf("%lld\n", Ans[i]);
	return 0;
}