AtCoder Beginner Contest 261 F // 树状数组
题目链接：F – Sorting Color Balls (atcoder.jp)
题意：
有n个球，球有颜色和数字。对相邻的两球进行交换时，若颜色不同，需要花费1的代价。求将球排成数字不降的顺序，所需的最小代价。
思路：
将完成排序所需的最小代价记作 cost，将颜色不同的逆序对（ i < j && xi > xj && ci ≠ cj ）数量记作 cnt ，则有 cost = cnt。证明如下：
-
可以构造出一种所需花费为 cnt 的排序方案：将这n个球按颜色切分，即切分成若干个颜色相同的连续区间，那么将每个区间进行排序，不需要花费任何代价，然后再进行冒泡排序，则花费代价恰为 cnt。因此有 cost ≧ cnt 。
-
再证明 cost ≤ cnt ：依然先将各个颜色相同的连续区间进行排序，那么不考虑颜色时，总的逆序对变为 cnt 。每次进行相邻数交换，则逆序对数量的变化可能为：+1、0、-1，那么要让逆序对数量变为 0，至少需要 cnt 次交换，因此有 cost ≤ cnt。
那么只需要求出 cnt：求出不考虑颜色时逆序对数量 totalCnt，在求出对于各个颜色，颜色相同的逆序对数量Cnti，因此：cnt = totalCnt – ∑Cnti 。
然后求逆序对，就是树状数组的经典应用了。
代码：
#include <bits/stdc++.h> #define LL long long #define lowbit(x) (x & -x) using namespace std; const int N = 300010; int n, c[N]; vector<int> v[N]; int tr[N]; void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; } LL sum(int x) { LL res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } int main() { cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &c[i]); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); v[0].push_back(x); //v[0]存储不考虑颜色时的值，后续求出不考虑颜色时的逆序对 v[c[i]].push_back(x); //v[ci]则存储考虑颜色时的值，后续求出相同颜色下的逆序对 } LL ans = 0; for(int i = 0; i <= n; i++) { for(auto& x : v[i]) { ans = ans + (i ? -1 : 1) * (sum(n) - sum(x)); add(x, 1); } for(auto& x : v[i]) add(x, -1); } cout << ans << endl; return 0; }
