题目链接：传送门

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

人生第一道树套树的题 这一题如果不带修改的话很明显可以用权值线段树做 因为对于一个点而言，它对答案产生的贡献就是它前面的数中比它大的数的个数加上它后面的数中比它小的数的个数 但是如果需要修改，我们还直接上线段树的话每一次修改的时间复杂度就会是O(NlogN)O(N log N)的，显然承受不了。 因此我们可以考虑套一层树状数组，每个树状数组上的点上开一颗线段树， 那么这样的话修改就变成O(log2N)O(log^2 N)的了， 只是需要注意线段树要动态开点，不然会MLE 然后愉快地上树状数组套权值线段树就可以了

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 <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
#define lowbit(x) (x & (-x))
using namespace std;
const int Maxn = 100000 + 100, Maxm = 50000 + 100, Maxt = 10000000 + 10;
int N, M;
int A[Maxn], Pos[Maxn], lson[Maxt], rson[Maxt], Tree[Maxt], Cnt;
inline void push_up(int x)
{
    Tree[x] = Tree[lson[x]] + Tree[rson[x]];
}
inline int query_seg(int root, int l, int r, int x, int y)
{
    if (!root) return 0;
//  if (x <= l && r <= y)
//      return Tree[root];
    if (x == l && r == y)
        return Tree[root];
    int mid = (l + r) >> 1;
    int Sum = 0;
    //if (x <= mid) Sum += query_seg(lson[root], l, mid, x, y);
    //if (y > mid) Sum += query_seg(rson[root], mid + 1, r, x, y);
//  push_up(root);
    if (y <= mid) return query_seg(lson[root], l, mid, x, y);
    else if (x > mid) return query_seg(rson[root], mid + 1, r, x, y);
    return query_seg(lson[root], l, mid, x, mid) + query_seg(rson[root], mid + 1, r, mid + 1, y);
//  return Sum;
}
inline void add_seg(int &root, int l, int r, int x, int v)
{
    if (!root) root = ++Cnt;
    if (l == r)
    {
        Tree[root] += v;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        add_seg(lson[root], l, mid, x, v);
    else 
        add_seg(rson[root], mid + 1, r, x, v);
    push_up(root);
}
inline int query_bit(int x, int l, int r)
{
    int Sum = 0;
    int fl = 0;
    while (x)
    {
        Sum += query_seg(x, 1, N, l, r);
        x -= lowbit(x);
    }
    return Sum;
}
inline void add_bit(int x, int y, int v)
{
    while (x <= N)
    {
        add_seg(x, 1, N, y, v);
        x += lowbit(x);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    Cnt = N;
    LL Ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &A[i]), Pos[A[i]] = i;
        Ans += (LL)query_bit(i - 1, A[i] + 1, N);
        add_bit(i, A[i], 1);
    }
    int x;
    for (int i = 1; i <= M; ++i)
    {
        printf("%lld\n", Ans);
        scanf("%d", &x);
        Ans -= (LL)query_bit(Pos[x] - 1, x + 1, N);
        Ans -= (LL)query_bit(N, 1, x - 1);
        Ans += (LL)query_bit(Pos[x] - 1, 1, x - 1);
        add_bit(Pos[x], x, -1);
    }
    return 0;
}