做这种题就是大胆列柿子

设已经匹配好的两串为$a,b$，加$x$

即$\sum\limits_{i=1}^n (a_i+x-b_i)^2$。

展开它

$\sum\limits _{i=1}^n {a_i}^2+{b_i}^2+x^2+2*x*a_i-2*x*b_i-2*a_i*b_i\\\sum\limits_{i=1}^na_i^2+\sum\limits_{i=1}^nb_i^2+n*x^2+2*x*(\sum\limits_{i=1}^na_i-\sum\limits_{i=1}^nb_i)-2*\sum\limits_{i=1}^na_ib_i$

发现前几项都是定值，就是$\sum\limits_{i=1}^na_ib_i$是个变量，变形$\sum\limits_{i=1}^na_{n-i+1}b_i$

把$a$倍长后，直接上$fft$，最大值从$n+1\sim 2*n$中找。

至于$x$的取值，由于$a_i,b_i\in[1,m]$，那么$w=a_i-b_i\in[m-1,-m-1]$

则$x\in[-m.m]$，暴力枚举$x$就好了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=1<<18;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct CP
{
    double x,y;
    CP(double x=0.0,double y=0.0):x(x),y(y){}
    CP operator +(const CP a)const{return CP(x+a.x,y+a.y);}
    CP operator -(const CP a)const{return CP(x-a.x,y-a.y);}
    CP operator *(const CP a)const{return CP(x*a.x-y*a.y,x*a.y+y*a.x);}
}f[N],g[N];
int tr[N],n,m;
void fft(CP *f,int op)
{
    for(int i=0;i<n;i++)
        if(tr[i]<i)swap(f[i],f[tr[i]]);
    for(int p=2;p<=n;p<<=1)
    {
        int len=p>>1;
        CP tg=CP(cos(2*pi/p),sin(2*pi/p)*op);
        for(int k=0;k<n;k+=p)
        {
            CP buf=CP(1,0);
            for(int l=k;l<k+len;l++)
            {
                CP t=buf*f[l+len];
                f[l+len]=f[l]-t;
                f[l]=f[l]+t;
                buf=buf*tg;
            }    
        }
    }
}
int a[N],b[N];
int main()
{
    qr(n),qr(m);int t=n,mx=m,s1=0,s2=0;
    for(int i=1;i<=n;i++)qr(a[i]),s1+=a[i]*a[i],s2+=2*a[i];
    for(int i=1;i<=n;i++)qr(b[i]),s1+=b[i]*b[i],s2-=2*b[i];
    for(int i=1;i<=n;i++)f[i-1].x=a[i],g[n-i]=b[i];
    for(int i=0;i<n;i++)g[i+n]=g[i];
    m=2*n-1;n--;
    for(m+=n,n=1;n<=m;n<<=1);
    for(int i=0;i<n;i++)
        tr[i]=tr[i>>1]>>1|((i&1)?n>>1:0);
    fft(f,1),fft(g,1);
    for(int i=0;i<n;i++)f[i]=f[i]*g[i];
    fft(f,-1);
    int w=0,ans=0x3f3f3f3f;
    for(int i=t-1;i<=2*t-1;i++)
        w=max(w,(int)(2*f[i].x/n+0.49));
    for(int c=-mx;c<=mx;c++)
    {
        int sum=s1+c*s2-w+t*c*c;
        ans=min(ans,sum);
    }
    qw(ans);puts("");
    return 0;
}