$O(n)$ 前缀和

关键观察

1. 基础逆序对计算：

   • 在二进制数组中，逆序对只可能出现在 1 在 0 前面的情况
   • 具体来说，对于每个 1 ，它后面有多少个 0 ，就会产生多少个逆序对

2. 翻转操作的影响：

   • 翻转一个元素可能增加或减少逆序对数量
   • 我们需要找到能使逆序对增加最多的翻转操作

3. 数学分析：

   • 设原始逆序对数量为 cnt
   • 对于位置 i 的元素 a[i] ：
     • 如果 a[i] = 0 ，翻转成 1 会减少 pre[i-1] 个逆序对，但会增加 (n-i)-(pre[n]-pre[i]) 个逆序对
     • 如果a[i] = 1 ，翻转成 0 会减少 (n-i)-(pre[n]-pre[i]) 个逆序对，但会增加 pre[i-1] 个逆序对

4. 最优策略：

   • 计算原始逆序对数量 cnt
   • 对于每个位置，计算翻转该元素带来的净收益
   • 选择净收益最大的翻转操作（如果为正）

代码实现

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n;
int a[N];
int pre[N]; // 前缀和数组，pre[i]表示前i个元素中1的个数

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i]; // 计算前缀和
    }
    
    LL cnt = 0, t = 0; // cnt: 原始逆序对数量，t: 最大净收益
    for(int i = 1; i <= n; i++) {
        LL x = pre[i - 1]; // 前i-1个元素中1的个数
        LL y = n - i - (pre[n] - pre[i]); // 后n-i个元素中0的个数
        
        if(a[i] == 0) {
            cnt += x; // 原始情况下，0会与前面的所有1形成逆序对
            t = max(t, y - x); // 翻转0->1的净收益
        } else {
            t = max(t, x - y); // 翻转1->0的净收益
        }
    }
    cout << cnt + t << endl; // 原始逆序对 + 最大净收益
}

int main() {
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}