P6186 [NOI Online #1 提高组]冒泡排序 逆序对

rhdeng · 2020-11-11 19:43:19 · 个人记录

传送~

Description

给你一个排列, 有两种操作:

1. 交换 x, x+1 位置上的两个数

2. 询问当前排列进行 k 轮冒泡排序后的逆序对个数

Solution

首先研究下题目给的冒泡排序的代码, 可以发现 i 位置上一次交换会进行, 当且仅当 i 前面有比 i 位置上的数更大的数, 并且交换过后 i 前面比它位置上更大的数的个数会减少 1.

因此可以维护 i 前面有多少个数比 i 位置上的数更大. 设它为 c_i, k 轮排序后, c_i 就变成了 \max(0, c_i-k). 答案就是

开两个树状数组分别维护 c_i 的前缀和 和 c_i 个数的前缀和, 用于查询比 k 大的 c_i 之和 与 比 k 大的 c_i 的个数, 用和减去个数乘 k 就好了.

Code

#include <bits/stdc++.h>

#define int long long

#define debug(x) cout << #x << " = " << x << endl;
#define swap Swap
#define max Max
#define min Min

using namespace std;

inline char gc() {
    static char buf[1000010], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf)+fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

template<typename T> inline void read(T& x) {
    char ch = getchar(); T a = 0, b = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') ch = getchar(), b = -1;
    while (ch >= '0' && ch <= '9') a = a*10+ch-'0', ch = getchar();
    x = a*b;
}

template<typename T> inline void Swap(T& x, T& y) {x = x^y; y = x^y; x = x^y;}
template<typename T> inline void chkmin(T& x, T y) {x = (y < x ? y : x);}
template<typename T> inline void chkmax(T& x, T y) {x = (y > x ? y : x);}
template<typename T> inline T Min(T x, T y) {return x < y ? x : y;}
template<typename T> inline T Max(T x, T y) {return x > y ? x : y;}

const int maxn = 2e5;

int n, m, a[maxn+10], c[maxn+10];

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

struct tree {
    int bt[maxn+10];

    void init() {
        memset(bt, 0, sizeof(bt));
    }

    void update(int x, int v) {
        if (!x) return;
        for (; x <= n; x += lowbit(x))
            bt[x] += v;
    }

    int query(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x))
            res += bt[x];
        return res;
    }
} t1, t2;

void modify(int x, int v) {
    t2.update(x, -1);
    t1.update(x, -x);
    t2.update(x+v, 1);
    t1.update(x+v, x+v);
}

signed main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    read(n); read(m);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    for (int i = 1; i <= n; ++i) {
        c[i] = i-1-t1.query(a[i]);
        t1.update(a[i], 1);
        t2.update(c[i], 1);
    }
    t1.init();
    for (int i = 1; i <= n; ++i)
        t1.update(i, i*(t2.query(i)-t2.query(i-1)));
    for (int i = 1; i <= m; ++i) {
        int ty, x;
        read(ty); read(x);
        if (ty == 1) {
            if (a[x] < a[x+1]) modify(c[x], 1), ++c[x];
            else modify(c[x+1], -1), --c[x+1];
            swap(a[x], a[x+1]);
            swap(c[x], c[x+1]);
        } else {
            if (x >= n) printf("0\n");
            else {
                int a = t1.query(n)-t1.query(x);
                int b = t2.query(n)-t2.query(x);
                printf("%lld\n", a-b*x);
            }
        }
    }
    return 0;
}