1215.小朋友排队(树状数组应用--逆序对个数)

题目如下：

思路 or 题解

我们可以得出交换的次数 >= 逆序对个数 k k k 我们可以发现 所有 位置 左边大于它的个数 + 右边小于它的个数和 k i k_i ki​ 等于 k ∗ 2 k*2 k∗2 我们可以简单证明出(感觉出)：答案就是 ∑ 1 n ( 1 + k i ) ∗ k i 2 \sum^n_1 \frac{(1 + k_i) * k_i}{2} ∑1n​2(1+ki​)∗ki​​

AC 代码如下： #define ll long long const int N = 1000009; int n, tre[N], cnt[N], s[N]; int lowbit(int x) { return x & -x; } void add(int x) { for (int i = x; i < N; i += lowbit(i)) tre[i]++; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tre[i]; return res; } void solve() { cin >> n; ll ans = 0; for (int i = 1; i <= n; i++) { cin >> s[i]; s[i]++; cnt[i] += query(N - 1) - query(s[i]); add(s[i]); } memset(tre, 0, sizeof tre); for (int i = n; i >= 1; i--) { cnt[i] += query(s[i] - 1); ans += (ll)(cnt[i] + 1) * cnt[i] / 2; add(s[i]); } cout << ans << '\n'; } int main() { buff; solve(); }