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;
}