• 可以看做将其中一个数列(假定为 \(a\) )都加上 \(c\) , \(c\) 可以为负数.易知这里 \(-m\leq c\leq m\).
• 记要求的答案为 \(ans\) , 大力拆开括号可得:

\[ ans=\sum{(a_i+c-b_i)^2}\\=\sum a_i^2+\sum b_i^2+n\cdot c^2+2c\cdot (\sum a_i-\sum b_i)-2\sum a_i b_i. \]

• 这里的 \(a,b\) 是原数列元素不变,通过旋转得到的.
• 其中前两项是确定的,中间两项只与 \(c\) 有关,最后一项只与旋转方式有关.
• \(c\) 的取值范围很小,可以枚举 \(c\) 求中间两项的最小值,而求最后一项的最大值,有一个做法:
• 将 \(a\) 翻转后重复一次,即拼接成 \(a'=a^Ra^R\),做卷积 \(a''=a'\otimes b\), 则 \(a''\) 的 \(n+1\) 至 \(2n\) 的项恰好对应了通过每种旋转方式后的 \(\sum a_i b_i\) ,可以通过验证得出.对这些项取一个最大值即可.
• 用 \(FFT\) 加速卷积过程,总时间复杂度为 \(O(nlogn)\) .

#include
    
     using namespace std;#define ll long long#define mp make_pair#define pii pair
     
      #define max(a,b) ((a) < (b) ? b : a)#define min(a,b) ((a) < (b) ? a : b)inline int read(){    int x=0;     bool pos=1;     char ch=getchar();    for(;!isdigit(ch);ch=getchar())        if(ch=='-')            pos=0;    for(;isdigit(ch);ch=getchar())        x=x*10+ch-'0';    return pos?x:-x;}void write(int x){    if(x>=10)        write(x/10);    putchar(x%10+'0');}void writeln(int x){    write(x);     puts("");}struct cp{    double x,y;    cp(double xx=0,double yy=0){x=xx;y=yy;}    cp operator +(const cp &b){return cp(x+b.x,y+b.y);}    cp operator -(const cp &b){return cp(x-b.x,y-b.y);}    cp operator *(const cp &b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}};const double PI=acos(-1.0);const int MAXN=6e5+10;cp omega[MAXN],inv[MAXN];int rev[MAXN];void init(int n,int lim){    for(int i=0; i
      
       >j)&1)                rev[i]|=1<<(lim-j-1);    }}void FFT(cp *a,int n,bool invflag){    for(int i=0; i
       
        >1;        cp wi=cp(cos(2*PI/l),sin(2*PI/l));        if(invflag)            wi=cp(cos(2*PI/l),-sin(2*PI/l));        for(int p=0; p