OiClass PU2TI P3186 小美的排队次数 题解

思路

以下格式模仿睿智的官方题解。

• \(10\,\%\) 做法：呵呵，对于这种神奇的算法还是表示不明觉厉。
• \(40\,\%\) 做法：呵呵，依题意模拟计数即可。
• \(100\,\%\) 做法：呵呵，随便做即可。考虑以下先做一轮，观察一下有什么性质。手磨样例，一轮以后是 1, 2, 3, 5, 4, 6 发现每一次只可能交换相邻的两个数，于是猜测逆序对。简单再次手磨以下， 1, 2, 3, 5, 4, 6 的逆序对个数是 \(1\) 个，巧了，过样例！下载个大样例，也过了，爽！然后自信提交，\(80 {\rm pts}\)​？十年 OI 一场空，不开 long long 见祖宗！。

补一句，树状数组跑的还是比线段树和归并快很多的。

image-20240619165706940

代码

#include <iostream>
#include <algorithm>

#define int long long
#define lowbit(x) (x & -x)

using namespace std;

int n, h[100009], t[100009];

void add(int x) {
    for (int i = x; i <= n; i += lowbit(i)) {
        t[i] += 1;
    }
}

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += t[i];
    }
    return res;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        int r = l;
        for (r; r <= n and h[r + 1] <= h[r] and h[r + 1] != 0; r++);
        if (l == r) {
            continue;
        }
        reverse(h + l, h + r + 1);
        cnt += 1;
        l = r;
    }
    for (int i = 1; i <= n; i++) {
        cnt += i - 1 - query(h[i]);
        add(h[i]);
    }
    cout << cnt;
}