You are given an array aa consisting of nn integers (it is guaranteed that nn is even, i.e. divisible by 22). All aiai does not exceed some integer kk.
Your task is to replace the minimum number of elements (replacement is the following operation: choose some index ii from 11 to nn and replace aiai with some integer in range [1;k][1;k]) to satisfy the following conditions:
- after all replacements, all aiai are positive integers not greater than kk;
- for all ii from 11 to n2n2 the following equation is true: ai+an−i+1=xai+an−i+1=x, where xx should be the same for all n2n2 pairs of elements.
You have to answer tt independent test cases.
The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.
The first line of the test case contains two integers nn and kk (2≤n≤2⋅105,1≤k≤2⋅1052≤n≤2⋅105,1≤k≤2⋅105) — the length of aa and the maximum possible value of some aiai correspondingly. It is guratanteed that nn is even (i.e. divisible by 22). The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤k1≤ai≤k), where aiai is the ii-th element of aa.
It is guaranteed that the sum of nn (as well as the sum of kk) over all test cases does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105, ∑k≤2⋅105∑k≤2⋅105).
For each test case, print the answer — the minimum number of elements you have to replace in aa to satisfy the conditions from the problem statement.
4
4 2
1 2 1 2
4 3
1 2 2 1
8 7
6 1 1 7 6 3 4 6
6 6
5 2 6 1 3 4
0 1 4 2
官方题解：
It is obvious that if we fix the value of xx then there are three cases for the pair of elements:
- We don't need to change anything in this pair;
- we can replace one element to fix this pair;
- we need to replace both elements to fix this pair.
The first part can be calculated easily in O(n+k)O(n+k), we just need to create the array of frequencies cntcnt, where cntxcntx is the number of such pairs (ai,an−i+1)(ai,an−i+1) that ai+an−i+1=xai+an−i+1=x.
The second part is a bit tricky but still doable in O(n+k)O(n+k). For each pair, let's understand the minimum and the maximum sum we can obtain using at most one replacement. For the ii-th pair, all such sums belong to the segment [min(ai,an−i+1)+1;max(ai,an−i+1)+k][min(ai,an−i+1)+1;max(ai,an−i+1)+k]. Let's make +1+1 on this segment using prefix sums (make +1+1 in the left border, −1−1 in the right border plus one and then just compute prefix sums on this array). Let this array be prefpref. Then the value prefxprefx tells the number of such pairs that we need to replace at most one element in this pair to make it sum equals xx.
And the last part can be calculated as n2−prefxn2−prefx. So, for the sum xx the answer is (prefx−cntx)+(n2−prefx)⋅2(prefx−cntx)+(n2−prefx)⋅2. We just need to take the minimum such value among all possible sums from 22 to 2k2k.
There is another one solution that uses scanline, not depends on kk and works in O(nlogn)O(nlogn) but it has no cool ideas to explain it here (anyway the main idea is almost the same as in the solution above).
利用前缀和：make +1 in the left border, −1 in the right border plus one and then just compute prefix sums on this array
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<int> cnt(2 * k + 1);
for (int i = 0; i < n / 2; ++i) {
++cnt[a[i] + a[n - i - 1]];
}
vector<int> pref(2 * k + 2);
for (int i = 0; i < n / 2; ++i) {
int l1 = 1 + a[i], r1 = k + a[i];
int l2 = 1 + a[n - i - 1], r2 = k + a[n - i - 1];
assert(max(l1, l2) <= min(r1, r2));
++pref[min(l1, l2)];
--pref[max(r1, r2) + 1];
}
for (int i = 1; i <= 2 * k + 1; ++i) {
pref[i] += pref[i - 1];
}
int ans = 1e9;
for (int sum = 2; sum <= 2 * k; ++sum) {
ans = min(ans, (pref[sum] - cnt[sum]) + (n / 2 - pref[sum]) * 2);
}
cout << ans << endl;
}
return 0;
}