给一个序列，我们使用冒泡排序法对它进行排序。请输出在排序过程中会进行多少次交换。
参考大佬：https://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html
#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include<set> #include #include #include #include #include #include using namespace std; #define inf 1<<30 #define eps 1e-7 #define LD long double #define LL long long #define maxn 1000005 struct node { int v, f; }b[maxn]; int aa[maxn], c[maxn], n; bool cmp(node A, node B) { return A.v < B.v; } int low(int x) { return x & (-x); } void updata(int p, int q) { while (p <= n) { c[p] += q; p += low(p); } } int sum(int p) { int ans = 0; while (p > 0) { ans += c[p]; p -= low(p); } return ans; } int main() { while (~scanf("%d", &n) ) { if (n == 0)break; int i; LL ans = 0; for (i = 1; i <= n; i++) { scanf("%d", &b[i].v); b[i].f = i; } sort(b + 1, b+n+1, cmp); for (i = 1; i <= n; i++) { aa[b[i].f] = i; } memset(c, 0, sizeof(c)); for (i = 1; i <= n; i++) { updata(aa[i], 1); ans += i - sum(aa[i]); } printf("%lld\n", ans); } }