# Codeforces 1343 D. Constant Palindrome Sum（差分数组）

## Description

You are given an array $a$ consisting of $n$ integers (it is guaranteed that $n$ is even, i.e. divisible by $2$). All $a_i$ does not exceed some integer $k$.

Your task is to replace the minimum number of elements (replacement is the following operation: choose some index $i$ from $1$ to $n$ and replace $a_i$ with some integer in range $[1,k]$) to satisfy the following conditions:

• after all replacements, all $a_i$ are positive integers not greater than $k$.
• for all $i$ from $1$ to $\frac{n}{2}$ the following equation is true: $a_i + a_{n – i + 1} = x$, where $x$ should be the same for all $\frac{n}{2}$ pairs of elements.
• You have to answer $t$ independent test cases.

## Input

The first line of the input contains one integer $t$ $(1\le t \le 10^4)$ — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ $(2 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5)$ — the length of $a$ and the maximum possible value of some $a_i$ correspondingly. It is guratanteed that $n$ is even (i.e. divisible by $2$). The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le k)$, where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ (as well as the sum of $k$) over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$, $\sum k \le 2 \cdot 10^5$).

## Output

For each test case, print the answer — the minimum number of elements you have to replace in $a$ to satisfy the conditions from the problem statement.

## Example input

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


## Example output

0
1
4
2


## 思路

1. 此时 $a[i] + a[n-i-1]=x$，则在这对中不需要操作
2. 每一对中最多操作一次的情况下，和的范围是 $[\min(a[i], a[n-i-1]) + 1,\max(a[i], a[n-i-1]) + k]$
3. 每一对中最多操作两次的情况下，和的范围是 $[2, k+k]$

## AC 代码

### 差分数组

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 4e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, k;
int a[maxn];
int cnt[maxn];
void solve() {
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n / 2; i++) {
int x = a[i];
int y = a[n - i - 1];
int line1 = min(x, y) + 1;
int line2 = max(x, y) + k;
cnt[2] += 2; // 最多两次操作的情况，花费 2
cnt[k + k + 1] -= 2;
cnt[line1] += -1; // 最多一次的情况，从 2 中 -1
cnt[line2 + 1] -= -1;
cnt[x + y] += -1; // 不操作的情况，再 -1
cnt[x + y + 1] -= -1;
}
int ans = INT_MAX;
for (int i = 2; i <= k + k; i++) {
cnt[i] += cnt[i - 1];
ans = min(cnt[i], ans);
}
cout << ans << endl;
}
int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
IO;
#endif // LOCAL_IM0QIANQIAN

int T;
cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve();
}
return 0;
}


### 线段树

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 4e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;
#define default_setv -1
int sumv[maxn << 2]; //四倍空间
int minv[maxn << 2];
int maxv[maxn << 2];
int setv[maxn << 2]; //初始值：-1
int a[maxn];

void maintain(int o, int L, int R) {
int lc = o << 1, rc = o << 1 | 1;
sumv[o] = minv[o] = maxv[o] = 0;
if (setv[o] != default_setv) {
sumv[o] = setv[o] * (R - L + 1);
minv[o] = maxv[o] = setv[o];
} else if (R > L) {
sumv[o] = sumv[lc] + sumv[rc];
minv[o] = min(minv[lc], minv[rc]);
maxv[o] = max(maxv[lc], maxv[rc]);
}
sumv[o] += addv[o] * (R - L + 1);
}

void pushdown(int o) {
int lc = o << 1, rc = o << 1 | 1;
if (setv[o] != default_setv) {
setv[lc] = setv[rc] = setv[o];
setv[o] = default_setv;
}
}
}

/*
* (这里的L,R必须是2的幂次)
*/
void update_add(int o, int L, int R, int y1, int y2, int v_add) {
int lc = o << 1, rc = o << 1 | 1;
if (y1 <= L && y2 >= R)
else {
pushdown(o);
int M = L + (R - L) / 2;
if (y1 <= M)
else
maintain(lc, L, M);
if (y2 > M)
else
maintain(rc, M + 1, R);
}
maintain(o, L, R);
}

/*
* o: 当前节点(1)，修改区间：[y1,y2] ，修改值：v_set，总区间：[L,R]
* (这里的L,R必须是2的幂次)
*/
void update_set(int o, int L, int R, int y1, int y2, int v_set) {
int lc = o << 1, rc = o << 1 | 1;
if (y1 <= L && y2 >= R) {
setv[o] = v_set;
} else {
pushdown(o);
int M = L + (R - L) / 2;
if (y1 <= M)
update_set(lc, L, M, y1, y2, v_set);
else
maintain(lc, L, M);
if (y2 > M)
update_set(rc, M + 1, R, y1, y2, v_set);
else
maintain(rc, M + 1, R);
}
maintain(o, L, R);
}

/*
* o: 当前节点(1)，查询区间：[y1,y2] ，初始累加(0)，总区间：[L,R]
* (这里的L,R必须是2的幂次)
*/
int _min, _max, _sum;
void query(int o, int L, int R, int y1, int y2, int add) {
if (setv[o] != default_setv) {
_sum += (add + setv[o] + addv[o]) * (min(R, y2) - max(L, y1) + 1);
} else if (y1 <= L && y2 >= R) {
_sum += sumv[o] + add * (R - L + 1);
_min = min(_min, minv[o] + add);
_max = max(_max, maxv[o] + add);
} else {
int M = L + (R - L) / 2;
if (y1 <= M)
if (y2 > M)
query(o * 2 + 1, M + 1, R, y1, y2, add + addv[o]);
}
}

/*
* o: 当前节点(1)，总区间：[L,R] (这里的L,R必须是2的幂次)
* 所有 setv 初始化为 -1，所有叶子节点 addv 为当前值
*/
void build(int o, int L, int R) {
if (L == R) {
setv[o] = default_setv;
addv[o] = sumv[o] = maxv[o] = minv[o] = a[L];
} else {
int M = L + (R - L) / 2;
int lc = o << 1, rc = o << 1 | 1;
build(lc, L, M);
build(rc, M + 1, R);

setv[o] = default_setv;
sumv[o] = sumv[lc] + sumv[rc];
maxv[o] = max(maxv[lc], maxv[rc]);
minv[o] = min(minv[lc], minv[rc]);
}
}

/*
* 测试函数，R 代表叶子节点个数
*/
void test(int R, int n) {
cout << "----------" << endl;
auto init = [&]() {
_sum = 0;
_min = INT_MAX;
_max = INT_MIN;
};
for (int i = 1; i <= n; i++) {
init();
query(1, 1, R, i, i, 0);
cout << i << " --> " << _sum << "\t " << _min << "\t " << _max << endl;
}
init();
query(1, 1, R, 1, R, 0);
cout << "total: " << _sum << endl;
cout << "----------" << endl;
}

int n, k, R;
void solve() {
map<int, int> cnt;
for (int i = 0; i < n / 2; i++) {
cnt[a[i] + a[n - i - 1]]++;
int x = a[i];
int y = a[n - i - 1];
int line1 = max(x, y) + k;
int line2 = min(x, y) + 1;
update_add(1, 1, R, line2, line1, 1);
update_add(1, 1, R, x + y, x + y, -1);
if (line1 < k + k)
update_add(1, 1, R, line1 + 1, k + k, 2);
if (line2 > 2)
update_add(1, 1, R, 2, line2 - 1, 2);
}
_min = INT_MAX;
query(1, 1, R, 2, k + k, 0);
cout << _min << endl;
}
int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
IO;
#endif // LOCAL_IM0QIANQIAN

int T;
cin >> T;
while (T--) {
cin >> n >> k;
memset(a, 0, sizeof(a));
R = 1;
while (R < k + k)
R <<= 1;
build(1, 1, R);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve();
}
return 0;
}


### 2 只已被捕捉

• 钻网 搜狗浏览器 Windows 7

春暖花开，下次再来！

• 千千 Chrome | 81.0.4044.129 Windows 10

欢迎常来哦~