上海计算机学会 2024年4月月赛 丙组T3 交换的次数

标签：逆序数、思维、前缀和
题意：给定一个长度为$n$的$01$序列，$1$和$0$相邻就将$1$调后面去，问最终调换的次数。
（$1\le n\le 300,000$）
题解：很典型的一个逆序数，求每个数后面有多少的比自己小的数，因为$n$比较大，两层循环去求逆序数肯定会超时，这边可以通过归并排序或者树状数组之类的数据结构去查询。但是这个序列中又只有$1$和$0$，那我们可以通过后缀和统计一下$0$的数量，到时候从前往后跑一下每个$1$的位置，统计一下每个$1$的位置后面有多少个$0$的数。
或者反过来想看看每个$0$之前有多少个$1$，直接正着跑一边，对应计数即可。下面给出两种算法的代码
这边注意一个细节，最坏情况 数量可能爆$int$，得开$longlong$。
代码 1：

#include <bits/stdc++.h>
using namespace std;string s;
int suf[300005]; // 后缀0的数量int main() {cin >> s;int n = s.size();long long ans = 0;for (int i = n - 1; i >= 0; i--) {suf[i] = suf[i + 1];if (s[i] == '0') suf[i]++;}for (int i = 0; i < n; i++) {if (s[i] == '1') ans += suf[i + 1];}cout << ans << endl;return 0;
}

代码 2：

#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;int n = s.size();long long ans = 0, cnt = 0; // cnt: 前缀1的数量for (int i = 0; i < n; i++) {if (s[i] == '1') cnt++;else ans += cnt;}cout << ans << endl;return 0;
}