AcWing 2819. 动态逆序对 题解

题目分析

本题给定(1)到(n)的一个排列，需要按照给定顺序依次删除(m)个元素，要求在每次删除一个元素之前统计整个序列的逆序对个数。逆序对定义为满足(i < j)且(A_i > A_j)的数对((i, j))的个数。

解题思路

本题采用归并排序结合树状数组的方法来求解。通过归并排序计算初始序列的逆序对个数，然后利用树状数组动态更新删除元素后逆序对个数的变化。
1. 定义数据结构：定义结构体Data来存储元素的值a、时间戳t（用于标记元素在删除过程中的顺序）和逆序对个数res。tr[N]为树状数组，pos[N]用于记录每个元素在初始序列中的位置。
2. 树状数组操作：实现树状数组的基本操作，包括lowbit函数计算二进制最低位，add函数更新树状数组，query函数查询前缀和。
3. 归并排序计算逆序对：merge_sort函数通过归并排序，在合并过程中利用树状数组统计逆序对个数。分左右两部分进行处理，分别统计逆序对并更新树状数组，最后合并结果。
4. 处理删除元素：读入初始排列和要删除的元素，为每个元素分配时间戳。根据时间戳调用归并排序计算逆序对个数，再通过累加和逆序输出得到每次删除前的逆序对个数。

代码逐段分析

1. 头文件和全局变量定义

#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];

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义LL为long long的别名。
• 定义常量N表示序列的最大长度。
• 变量n表示初始元素的个数，m表示删除的元素个数。
• 定义结构体Data，包含元素的值a、时间戳t和逆序对个数res。q[N]和w[N]分别用于存储原始序列和归并排序过程中的临时序列。
• tr[N]是树状数组，pos[N]用于记录每个元素在初始序列中的位置。

• 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;
}

• lowbit函数返回x在二进制表示下的最低位。
• add函数用于在树状数组的位置x上加上值v，通过不断加上lowbit(i)来更新相关位置。

• query函数用于查询树状数组中位置x的前缀和，通过不断减去lowbit(i)来累加相关位置的值。

• 归并排序与逆序对统计函数

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 (int i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

• 该函数使用归并排序来计算逆序对个数。如果l >= r，则说明子数组只有一个元素或为空，直接返回。
• 计算中点mid，并递归地对左右子数组进行归并排序。
• 第一部分：从右半部分和左半部分的末尾开始比较，若左半部分元素值大，则将其时间戳加入树状数组；若右半部分元素值小，则统计其逆序对个数（通过查询树状数组），最后清除左半部分加入树状数组的元素。
• 第二部分：从左半部分和右半部分的开头开始比较，类似第一部分操作，统计逆序对个数并更新树状数组。

• 第三部分：将左右两部分合并到临时数组w，再复制回原数组q。

• 主函数

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;
}

• 读入初始元素个数n和删除元素个数m，以及初始排列，记录每个元素在初始序列中的位置。
• 读入要删除的元素，为其分配从n开始递减的时间戳，并将其在pos数组中的位置设为-1。
• 为未被删除的元素分配剩余的时间戳。
• 调用merge_sort函数计算逆序对个数。
• 将每个元素的逆序对个数按时间戳存入ans数组，然后进行累加。
• 逆序输出每次删除前的逆序对个数。

时间复杂度分析

• 归并排序的时间复杂度为(O(n\log n))，其中(n)是元素个数。
• 树状数组的操作时间复杂度为(O(\log n))，在归并排序中对树状数组的操作次数为(O(n))，所以树状数组相关操作的总时间复杂度为(O(n\log n))。
• 总体时间复杂度为(O(n\log n))。

空间复杂度分析

主要空间消耗在于存储序列的数组、树状数组和临时数组等，空间复杂度为(O(n)) 。