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