动态逆序对问题

解题思路

本题要求删掉序列中若干个元素，每删掉一个元素之前，统计一下序列中逆序对的数量。

设 $P_i$ 表示第 $i$ 个元素的下标

对于每个元素 $i$，和他构成逆序对的数满足 $P_j$ < $P_i, A_j$ > $A_i$，这样就有两维的条件了，因此我们考虑再加一维条件，这样就可以用 CDQ 分治来做三维偏序问题。第三维就要用删除元素上入手，这里可以用一个时间戳来模拟删除的过程，对于每个元素 $i$，用 $T_i$ 表示 $i$ 被删除的时间。为了搭配第三维用树状数组来求前缀和，我们分配时间戳的时候可以倒着分配，对于第一个被删除的数时间戳为 $n$，第二个被删除的数时间戳为 $n-1$，第 $m$ 个被删除的数时间戳为 $n-m+1$，而剩下的 $n-m$ 个数，我们只需要用剩下的 $1\sim n-m$ 个时间戳随机分配即可

然后由于我们每次删除之前，我们需要统计有多少个逆序对，因此我们统计答案的时候应该按照时间来看，对于每个时间戳 $T_i$ 来说，我们要统计当前还存在的元素中和 $i$ 构成逆序对的数的个数。记作 $s_i$。

那么对于删除第 $i$ 个元素之前，逆序对的数量，此时还剩下的数就是时间戳为 $1 \sim i$ 的所有数构成的逆序对，也就是 $s_1+s_2+…+s_i$。

此时对于 $T_i$，当前还存在的元素和 $i$ 构成逆序对的数 $j$ 首先需要满足 $T_j$ < $T_i$，然后还要满足 $P_j$ < $P_i,A_j$ > $A_i$ 或 $P_i$ < $P_j,A_i$ > $A_j$ 这两个情况中的一种。可以发现这两个情况各自都是一个三维偏序，因此我们需要分别求两个三维偏序，然后将答案累加在一起。

我们令 $P_i,A_i,T_i$ 分别为一、二、三维，第一维用三关键字排序来满足，然后考虑后面两维，这里以 $P_j$ < $P_i,A_j$ > $A_i,T_j$ < $T_i$ 为例，首先 $i,j$ 有三种情况，一种是都在左半区间，一种是都在右半区间，一种是分别在左、右区间，前两种情况直接递归考虑，然后考虑第三种情况，由于已经满足 $P_j$ < $P_i$，因此 $j$ 在左半区间，$i$ 在右半区间，双指针要找出所有 $A_j$ > $A_i$ 的数，因此两个指针需要从右往左枚举，对于每个 $i$，找到最大的 $j$ 满足 $A_j$ < $A_i$，此时左半区间中 $j$ 后面的所有数都满足 $A_j$ > $A_i$，然后从这一部分中找出满足 $T_j$ < $T_i$ 的所有数，就用树状数组求一下 $1 \sim T_i$ 中出现的数的个数，更新与 $i$ 有关的逆序对的数量，$j$ 每次左移需要对应维护树状数组。另一种情况的三维偏序类似。

然后这里有一个性质，就是题目给定的序列最开始就是按照下标给出的，因此这个序列本身就是按照 $P_i$ 排好序的，由于 $P_i$ 是第一关键字，所有元素的下标又都不相同，因此整个序列最开始就已经按照三关键字排好序了，因此第一步排序的过程可以省略掉，而省略掉之后就会发现 $P_i$ 这一维就不再会被用到了，所以 $P_i$ 这一维的信息可以不用存。

C++ 代码

#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; //a, t 表示后两维，res 记录当前元素和剩余元素构成的逆序对的数量
}q[N], w[N]; //存储三维元素，w 是临时数组
int pos[N]; //pos[i] 表示数值 i 所在的下标
int tr[N]; //树状数组
LL res[N]; //记录答案

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c) //树状数组插入一个数
{
    for(int i = x; i < N; i += lowbit(i)) tr[i] += c;
}

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) //CDQ 分治
{
    if(l >= r) return;

    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    //情况 1
    int i = mid, j = r;
    while(i >= l && j >= mid + 1)
        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 + 1) q[j].res += query(q[j].t - 1), j--; //不排序，因此左区间不需要遍历完
    for(int k = i + 1; k <= mid; k++) add(q[k].t, -1); //将左区间修改的值还原

    //情况 2
    i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i].a > q[j].a) add(q[j].t, 1), j++;
        else q[i].res += query(q[i].t - 1), i++;
    while(i <= mid) q[i].res += query(q[i].t - 1), i++; //不排序，因此右区间不需要遍历完
    for(int k = mid + 1; k <= j - 1; 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];
}

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); //CDQ 分治

    //处理答案并输出
    for(int i = 0; i < n; i++) res[q[i].t] = q[i].res;
    for(int i = 2; i <= n; i++) res[i] += res[i - 1];
    for(int i = 0, j = n; i < m; i++, j--) printf("%lld\n", res[j]);

    return 0;
}