CodeForces 1343D Constant Palindrome Sum

题意

多组样例

给一个长度为$n$（$n$一定为偶数）的数组$a[]$，给一个正整数$k$，保证数组内元素为小于等于$k$的正整数，你可以每次将数组的一个元素变为小于等于$k$的正整数，问最少多少次操作后，数组能满足对于任意$i$，有$a[i]+a[n-i+1]=x$，$x$为任意值，即所有$a[i]+a[n-i+1]$相等

分析

枚举$x$然后判定肯定是不现实的，考虑分析$a[i]+a[n-i+1]$的性质，此处设$j=n-i+1$

两个数字都不改变，得到的和为$a[i]+a[j]$
改变一个数字，可以得到的和为$[\min(a[i],a[j])+1,\max(a[i],a[j])+k]$区间中的任意一个数（将较大数变为$1$得到最小和，将较小数变为$k$得到最大和）
改变两个数字，可以得到的和为$[2,2*k]$区间中的任意一个数

综上，对于($i,j)$，对于$[2,\min(a[i],a[j])]$的贡献为$2$，对于$[\min(a[i],a[j])+1,a[i]+a[j]-1]$的贡献为$1$，对于$a[i]+a[j]$的贡献为$0$，对于$[a[i]+a[j]+1,\max(a[i],a[j])+k]$的贡献为$1$，对于$[\max(a[i],a[j])+k+1,2*k]$的贡献为$2$

遍历每一组数字，我们可以得到这对数字对$[2,2*k]$区间内的$x$的贡献，然后取操作数最小的$x$的操作数即可

由于是区间贡献，采取前缀和数组或者树状数组皆可，这里采取前缀和数组

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
//#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 4e5 + 5;
const int mod = (ll) 1e9 + 7;
const int inf = 0x3f3f3f3f;
int T = 1;
int n, a[maxn], k;
int sum[maxn];

void solve() {
    cin >> n >> k;
    rep(i, 1, n)cin >> a[i];
    rep(i, 1, 2 * k)sum[i] = 0;
    rep(i, 1, n / 2) {
        int now = a[i] + a[n - i + 1];
        int maxx = max(a[i], a[n - i + 1]) + k + 1;
        sum[2] += 2;
        --sum[min(a[i], a[n - i + 1]) + 1];
        --sum[now];
        ++sum[now + 1];
        ++sum[maxx];
    }
    int ans = inf;
    rep(i, 2, 2 * k)sum[i] = sum[i - 1] + sum[i], ans = min(ans, sum[i]);
    cout << ans << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}