求助dalao
查看原帖
求助dalao
365433
Mark_M楼主2023/1/27 20:18
#include<iostream>
#define N int(1e5+5)
using namespace std;

typedef long long ll;
ll n, a[N * 4], tree[N * 4];

inline ll lowbit(ll x) {
	return x & -x;
}

void update(ll p,ll v) {
	for (ll i = p; i <= n; i += lowbit(i)) {
		tree[i] += v;
	}
}

ll sum(ll p) {
	ll ans = 0;
	for (ll i = p; i >= 1; i -= lowbit(i)) {
		ans += tree[i];
	}
	return ans;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	int r = n - 1;
	while (r > 0 && a[r] < a[r - 1]) {
		r--;
	}
	cout << r << endl;

	for (int i = r + 1; i <= n; i++) {
		update(a[i], 1);
	}
	for (int i = 1; i <= r; i++) {
		cout << r - i + sum(a[i])<<' ';
		update(a[i], 1);
	}
	cout << endl;
	return 0;
}
2023/1/27 20:18
加载中...