[AH2017/HNOI2017]礼物

题解：

水题

化简一波式子会发现就是个二次函数再加上一个常数

而只有常数中的-2sigma(xiyi)是随移动而变化的

所以只要o（1）求出二次函数最大值然后搞出sigma(xiyi)就可以了

这个东西显然只要将一个倒序相乘就可以了

被这个m要乘2坑了一波。。。调了半天才过样例

代码：

#include <bits/stdc++.h>

using namespace std;

#define N 200000

#define dob complex<double>

const double pi=acos(-1.0);

int r[N],sum[N],n,m,k,l;

dob a[N],b[N];

void fft(dob *a,int o)

{

    for (int i=;i<n;i++)

      if (i>r[i]) swap(a[i],a[r[i]]);

    for (int i=;i<n;i*=)

    {

        dob wn(cos(pi/i),sin(pi*o/i)),x,y;

        for (int j=;j<n;j+=(i*))

        {

            dob w(,);

            for (int k=;k<i;k++,w*=wn)

            {

                x=a[j+k]; y=w*a[i+j+k];

                a[j+k]=x+y,a[i+j+k]=x-y;

            }

        }

    }

}

void query()

{

    for (n = ; n <= m; n <<= ) l++;

    for (int i=;i<n;i++) r[i]=(r[i/]/)|((i&)<<(l-));

    fft(a,),fft(b,);

    for (int i=;i<n;i++) a[i]*=b[i];

    fft(a,-);

    for (int i=;i<=m*+;i++) sum[i]=(a[i].real()/n+0.5);

}

int main()

{

  freopen("noip.in","r",stdin);

  freopen("noip.out","w",stdout);

  std::ios::sync_with_stdio(false);

  cin>>m>>k; int x,now=,ans=;

  for (int i=;i<m;i++)

  {

    cin>>x; now+=x; ans+=x*x; a[i]=x;

  }

  for (int i=m-;i>=;i--)

  {

    cin>>x; now-=x; ans+=x*x; b[i]=x;

  }

  int y=-now/m;

  int minn=1e9;

  for (int i=y-;i<=y+;i++)

    minn=min(m*i*i+*i*now,minn);

  ans+=minn;

  int tmp=m; m*=;

  query();

  m=tmp;

  int maxn=sum[m-];

  for (int i=m;i<*m;i++) maxn=max(sum[i]+sum[i-m],maxn);

  ans-=*maxn;

  cout<<ans<<endl;

  return ;

}