题解 P3149 【排序】

· · 题解

Solution:

看到这道题，首先想到排过序的数之间的逆序对都被消掉了。假设当前的已经给 \le a_k 的数排了序。

则对于其它的逆序对分两种：

  1. 一个 \le a_k 的数与一个 >a_k 的数组成。对于这个 >a_k 的数，无论\le a_k 的数怎么排，它贡献的逆序对个数都是一样的，所以不用管。

  2. 两个 >a_k 的数组成。这种明显个数不变也不用管。

对于一个操作 a_k，如果之前存在一个操作 a_{k^{\prime}} 使得 a_{k^{\prime}}\ge a_k ，则这个操作不用考虑，直接输出上一次询问的答案。

对于一个要考虑的操作 k。排除了上面两种逆序对，我们就要在总的逆序对个数中减去所有 \le a_k 的数构成的逆序对。预处理 \le i 的数之间产生的逆序对记为 s_i。树状数组预处理出来即可。

至于这个预处理的过程，简要说一下（这也是我想得最久的地方）：从右往左扫描数组，遇到一个数 a_i，s_{a_i} += 目前遇到过的比 a_i 小的数。原理比较明显。

然后对 s_i 做个前缀和。

Code:

#include <cstdio>
#include <algorithm>
#define int long long

struct node {
    int id, v;
    inline bool operator < (const node x) const {return v < x.v;}
} b[300005];
inline bool operator < (const int x, const node y) {return x < y.v;}
int a[300005], c[300005], s[300005], n, N;
inline void update(const int x) {
    for (int i(x); i <= n; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
    int sum(0);
    for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
    return sum;
}

signed main() {
    int m, last(0);
    scanf("%lld%lld", &n, &m);
    for (int i(1); i <= n; ++ i) scanf("%lld", &b[i].v), b[i].id = i;
    std::sort(b + 1, b + n + 1);
    a[b[1].id] = 1;
    for (int i(2); i <= n; ++ i)
    a[b[i].id] = (b[i].v != b[i - 1].v) + a[b[i - 1].id];
    for (int i(n); i >= 1; -- i)
        s[a[i]] += query(a[i]), update(a[i]);
    N = a[b[n].id];
    for (int i(2); i <= N; ++ i) s[i] += s[i - 1];
    printf("%lld\n", s[N]);
    a[0] = -0x3fffffff;
    while (m --) {
        int k;
        scanf("%lld", &k);
        if (a[k] < a[last]) k = last;
        last = k;
        printf("%lld\n", s[N] - s[a[k]]);
    }
    return 0;
}

逆序对很玄，讨论区有说，另外我让小粉兔大佬换数据了不过暂时还没换。相信粉兔不会咕多久qwq。