CF1343D Constant Palindrome Sum

You are given an array a consisting of n integers (it is guaranteed that n is even, i.e. divisible by 2). All ai 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 ai with some integer in range [1;k][1;k]) to satisfy the following conditions:

  • after all replacements, all ai are positive integers not greater than k;
  • for all i from 1 to n/2 the following equation is true: ai+an−i+1=x, where x should be the same for all n2 pairs of elements.

You have to answer t independent test cases.

每一对数，当 $x \in [min(a_i,a_{n−i+1})+1;max(a_i,a_{n−i+1})+k] $, 至多只需要修改一个，否则需要修改两个；特别的，当 $x=a[i]+a[n-i+1]$ 时，无需修改；使用前缀和，$d[min(a_i,a_{n−i+1})+1]$ = -1; $d[max(a_i,a_{n−i+1})+k+1]=1$ 因为可能多个值相同所以用 $++,–$ .

对于 $x=a[i]+a[n-i+1]$ ,$d[a[i]+a[n-i-1]]–; d[a[i]+a[n-i-1]+1]++; $

所以对于 i 需要修改 $d[max(a_i,a_{n−i+1})+k] - d[min(a_i,a_{n−i+1})+1]$ 次。

然后，从左到右扫描一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int MAX=200000+10;
int t,n,k,a[MAX],d[MAX*2],ans;
int main(){
	//freopen("in","r",stdin);
	sf(t);
	while(t--){
		ans = INF;
		mem(d,0);
		sf(n);sf(k);
		fi(i,0,n) sf(a[i]);
		fi(i,0,n/2){
			d[0]+=2;
			d[min(a[i],a[n-i-1])+1]--;
			d[max(a[i],a[n-i-1])+k+1]++;
			d[a[i]+a[n-i-1]]--;
			d[a[i]+a[n-i-1]+1]++;
		}
		fi(i,1,k*2+1){
			d[i]+=d[i-1];
			ans = min(ans,d[i]);
		}
		pfn(ans);
	}
	return 0;
}