309924: CF1760E. Binary Inversions
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:24
Solved:0
Description
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