Codeforces 636(Div. 3)D. Constant Palindrome Sum（差分数组）

昨晚div.3的D题，1个多小时，一点头绪没有，今天晚上补题的时候才发现我tm题意读错了！！！啊啊啊啊啊！！！！！

我就说嘛！

那个区间 [ 1 ; k ] 是1到k的所有数字，而不是数组[1,k]中的数，我以为是后者，一直在想确定x后两个数加起来还要判断能不能等于x，因为数组[1,k]中的数可是不确定的

今天才反应过来题意读错了！（虽然要是没读错题也不一定能做出来，但总比读错了题一点思路没有强呀！）

枚举x，x的范围是[2,2*k]

定义一个数组vis

vis[i]表示当x=i时有多少对（a[j],a[n-j+1]）和为x

这个循环一遍即可求出

定义数组cis和数组p

对于一对数（a[i],a[n-i+1]）,首先a[i]+a[n-i-1]不需要修改任何数

而区间 [ min(a[i],a[n-i+1])+1 , max(a[i],a[n-i+1])+k]中的数都可以用这一对数只修改一个数的前提下得到，p数组是cis数组的差分数组

因此cis[i]表示当x=i是有多少对（a[j],a[n-j+1]）只修改一个数即可得到x

对于差分数组，当我们要计算区间修改时，可利用差分数组

比如数组a={1,2,3,4,5,6,7,8,9}

则差分数组p[i]=a[i]-a[i-1]

然后假设给数组a的区间[l,r]中加上值k

可进行如下操作

p[l] + = k;

p[r+1] - = k

最后在通过差分数组算出原数组即可

即a[i]=p[i]+a[i-1]

可见，当需要多次修改，单次查询时，差分数组似乎比线段树要好写一点。。。。

最后跑一遍x的取值取最小值即可

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int l=9999999,r=-1;
int a[200005];
int vis[400005];
int cis[400005];
int p[400005];
int main()
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++)
        {scanf("%d",&a[i]);}
        for(int i=1;i<=2*k+1;i++)
        {vis[i]=0;cis[i]=0;p[i]=0;}
        for(int i=1;i<=n/2;i++)
        {
            int x=a[i]+a[n-i+1];
            int l=min(a[i],a[n-i+1])+1;
            int r=max(a[i],a[n-i+1])+k;
            vis[x]++;
            p[l]+=1;p[r+1]-=1;
            p[x]+=(-1);p[x+1]-=(-1);
        }
        for(int i=2;i<=2*k;i++)
        {cis[i]=p[i]+cis[i-1];}
        int minn=99999999;
        for(int i=2;i<=2*k;i++)
        {
            int ans=n;
            ans-=2*vis[i];
            ans-=cis[i];
            minn=min(ans,minn);
        }
        printf("%d\n",minn);
    }
    return 0;
}