Binary Inversions

题意翻译

给定长度为 $n$ 的 $01$ 串，问至多将一个数字取反后逆序对的数量最大是多少。

题目描述

You are given a binary array $ ^{\dagger} $ 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 $ ^{\ddagger} $ the array can have after performing at most one operation? $ ^\dagger $ A binary array is an array that contains only zeroes and ones. $ ^\ddagger $ The number of inversions in an array is the number of pairs of indices $ i,j $ such that $ i<j $ and $ a_i > a_j $ .

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) — the length of the array. The following line contains $ n $ space-separated positive integers $ a_1 $ , $ a_2 $ ,..., $ a_n $ ( $ 0 \leq a_i \leq 1 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

3
7
1
13
2

说明

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.

**题意翻译**

给定一个长度为 $ n $ 的由 $ 0 $ 和 $ 1 $ 组成的字符串，问在至多将一个数字取反的情况下，逆序对的数量最大是多少。

**题目描述**

给你一个长度为 $ n $ 的二进制数组 $ ^{\dagger} $。你可以最多进行一次操作，在操作中，你可以选择任意一个元素并将其翻转：将 $ 0 $ 变为 $ 1 $ 或者将 $ 1 $ 变为 $ 0 $。

在最多进行一次操作后，数组可以达到的最大逆序对数是多少？

$ ^\dagger $ 二进制数组是一个只包含零和一的数组。

$ ^\ddagger $ 数组中的逆序对数是指满足 $ i a_j $ 的索引对 $ i,j $ 的数量。

**输入输出格式**

**输入格式**

输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。

每个测试案例的第一行包含一个整数 $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) —— 数组的长度。

接下来的行包含 $ n $ 个由空格分隔的正整数 $ a_1 $, $ a_2 $,..., $ a_n $ ( $ 0 \leq a_i \leq 1 $ ) —— 数组的元素。

保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot10^5 $。

**输出格式**

对于每个测试案例，输出一个整数 —— 在最多进行一次操作后，数组可以达到的最大逆序对数。

**输入输出样例**

**输入样例 #1**

```
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
```

**输出样例 #1**

```
3
7
1
13
2
```

**说明**

对于第一个测试案例，初始的逆序对由索引对 ( $ 1, 2 $ )，( $ 1, 4 $ )，( $ 3, 4 $ ) 组成，总共是 $ 3 $ 对，这已经是可能的最大值。

对于第二个测试案例，初始的逆序对由索引对 ( $ 2, 3 $ )，( $ 2, 4 $ )，( $ 2, 6 $ )，( $ 5, 6 $ ) 组成，总共是四对。但是，通过翻转第一个元素，数组变为 $ {1, 1, 0, 0, 1, 0} $，其逆序对由索引对 ( $ 1, 3 $ )，( $ 1, 4 $ )，( $ 1, 6 $ )，( $ 2, 3 $ )，( $ 2, 4 $ )，( $ 2, 6 $ )，( $ 5, 6 $ ) 组成，总共达到七对逆序对，这是可能的最大值。**题意翻译** 给定一个长度为 $ n $ 的由 $ 0 $ 和 $ 1 $ 组成的字符串，问在至多将一个数字取反的情况下，逆序对的数量最大是多少。 **题目描述** 给你一个长度为 $ n $ 的二进制数组 $ ^{\dagger} $。你可以最多进行一次操作，在操作中，你可以选择任意一个元素并将其翻转：将 $ 0 $ 变为 $ 1 $ 或者将 $ 1 $ 变为 $ 0 $。 在最多进行一次操作后，数组可以达到的最大逆序对数是多少？ $ ^\dagger $ 二进制数组是一个只包含零和一的数组。 $ ^\ddagger $ 数组中的逆序对数是指满足 $ i a_j $ 的索引对 $ i,j $ 的数量。 **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 10^4 $ ) —— 测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数 $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) —— 数组的长度。 接下来的行包含 $ n $ 个由空格分隔的正整数 $ a_1 $, $ a_2 $,..., $ a_n $ ( $ 0 \leq a_i \leq 1 $ ) —— 数组的元素。 保证所有测试案例中 $ n $ 的总和不超过 $ 2\cdot10^5 $。 **输出格式** 对于每个测试案例，输出一个整数 —— 在最多进行一次操作后，数组可以达到的最大逆序对数。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 3 7 1 13 2 ``` **说明** 对于第一个测试案例，初始的逆序对由索引对 ( $ 1, 2 $ )，( $ 1, 4 $ )，( $ 3, 4 $ ) 组成，总共是 $ 3 $ 对，这已经是可能的最大值。 对于第二个测试案例，初始的逆序对由索引对 ( $ 2, 3 $ )，( $ 2, 4 $ )，( $ 2, 6 $ )，( $ 5, 6 $ ) 组成，总共是四对。但是，通过翻转第一个元素，数组变为 $ {1, 1, 0, 0, 1, 0} $，其逆序对由索引对 ( $ 1, 3 $ )，( $ 1, 4 $ )，( $ 1, 6 $ )，( $ 2, 3 $ )，( $ 2, 4 $ )，( $ 2, 6 $ )，( $ 5, 6 $ ) 组成，总共达到七对逆序对，这是可能的最大值。