E. Binary Inversions——前缀+后缀

You are given a binary array† of length n. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a 0 into a 1 or vice-versa.

What is the maximum number of inversions‡ the array can have after performing at most one operation?

† A binary array is an array that contains only zeroes and ones.

‡ The number of inversions in an array is the number of pairs of indices i,j such that iaj.

Input
The input consists of multiple test cases. The first line contains an integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤2⋅105) — the length of the array.

The following line contains n space-separated positive integers a1, a2,…, an (0≤ai≤1) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output
For each test case, output a single integer — the maximum number of inversions the array can have after performing at most one operation.

Example
inputCopy
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
outputCopy
3
7
1
13
2
Note
For the first test case, the inversions are initially formed by the pairs of indices (1,2), (1,4), (3,4), being a total of 3, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices (2,3), (2,4), (2,6), (5,6), being a total of four. But, by flipping the first element, the array becomes 1,1,0,0,1,0, which has the inversions formed by the pairs of indices (1,3), (1,4), (1,6), (2,3), (2,4), (2,6), (5,6) which total to 7 inversions which is the maximum possible.

分析

1. 题意：找一个序列中的1 0个数（可以不连续），序列每次可以翻转一个数，然后找拥有最大的 1 0个数，当然也可以不翻转，只要1 0 个数所有情况最大即可；
2. 一开始直接暴力TLE了，然后看网上题解用前缀、后缀来解决；前缀数组fro存每个位置的数之前的所有0、1的个数，后缀数组back存储每个位置的数之后的所有0、1的个数；
3. 先找出来不进行翻转的答案数ans，然后逐个枚举，分别去判断翻转一个数的情况；

• 当前要翻转的数原来为1 (a[i]=1) 时，那么需要减去其位置后面的0的个数，因为1将要走了，后面的0和1组成的cp要分开了，需要加上其位置前面1的个数，因为a[i]=1翻转成0，使前面的1可以和其组cp；
• 当前要翻转的数原来是0时（将要变为1），那么需要加上其位置后面0的个数，因为新的1来了，能组cp了，需要减去其位置前面1的个数，因为0已经走了（0将翻转为1），所以这对cp要分开了；

4. 细节：需要注意翻转时，是对原方案数的操作，所以需要一个临时变量存刚开始一个数都没被翻转的ans，后面翻转后需要减、加操作都是对temp操作的，而不是ans（因为ans在变，翻转后可能使ans增大），以及结果需要用long long存储；
5. 这道题有的地方卡了好久，思维真的不太行啊，还带多练啊，向浩哥看齐；

#include

using namespace std;

typedef long long ll;

int t, n;
int a[200005];
int fro[2][200005];//前缀
int back[2][200005];//后缀

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        //求前缀，求i前面1的个数和0的个数
        int one = 0, zero = 0;
        for (int i = 1; i <= n; ++i) {
            fro[1][i] = one;
            fro[0][i] = zero;
            if (a[i])
                one++;
            else
                zero++;
        }
        //求后缀，每个位置后面的1和0的个数
        one = 0, zero = 0;
        for (int i = n; i >= 1; --i) {
            back[1][i] = one;
            back[0][i] = zero;
            if (a[i])
                one++;
            else
                zero++;
        }
        ll ans = 0;
        //不翻转时候
        for (int i = 1; i <= n; ++i) {
            if (a[i]) {
                ans += back[0][i];
            }
        }
        //逐个翻转判断
        ll temp = ans;//不翻转的方案数
        for (int i = 1; i <= n; ++i) {
            //把1变为0，方案数temp 减1后面是0的个数，加1前面是1的个数
            if (a[i]) {
                ans = max(ans, (temp - back[0][i] + fro[1][i]));//这里是对temp操作的，在他基础上变化方案数
            } else {
                //0变为1，方案数 减0前面1的个数，加0后面0的个数
                ans = max(ans, (temp - fro[1][i] + back[0][i]));
            }
        }
        cout << ans << endl;
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62