Description

小明有一个含有n个数的数列 \(a_1,a_2,\cdots,a_n\) 。

他定义一个数列的积为\(\sum_{i=1}^n\sum_{j=i}^n|a_i-a_j|*(j-i)\)。

他发现算出数列积实际上非常简单。因此他现在有了一个绝妙的主意。

他有Q个询问。

对于每个询问会给定两个参数\(l,r\) 。

他想知道的是，将\(a_l,a_{l+1},\cdots,a_r\)拿出来成为一个数列，问该数列的数列积是多少。

由于答案很大，他表示只要求出数列积对 \(2^{64}\) 取模后的值就可以了。

Solution

没有修改，考虑区间扩大缩小答案的增减量。

先讲讲0分做法，我们发现式子贡献可以拆开，维护四个值：个数，\(i\)的和，\(a_i\)的和，\(a_i\cdot i\)的和。于是有经典莫队算法，时间复杂度可以达到\(O(n\sqrt n log_2n)\)级别。此时如果运气好就可以过了。

将一个理论更优的做法：把序列分块，然后每一块的贡献可以暴力算。

考虑块与块之间的贡献，我们对于每一块维护它的排序块，枚举后面的块的排序块，用指针扫一下前面的排序块，算一下贡献即可。

然后就可以算第\(l\)块到第\(r\)块的贡献。

对于一个询问，它包含中间的完整块部分，还有左右的多余部分。

考虑多余部分怎么计算，先计算左（右）边自己的贡献：可以设一个\(f_{i,j}\)表示从\(i\)到\(i+j\)的贡献，可以预处理；然后计算数对分别在左右多余部分的贡献：把多余部分标记，然后枚举右边多余部分所在的排序块，左边指针扫，遇到标记就加入即可。

还有左右多余元素与中间块的贡献：把所有元素排序，枚举每个块，然后计算一个元素与一个块的贡献，计算方法类似前面，但要判断一下元素与块的前后关系。

有了一个元素与一个块的贡献，就可以计算一个元素与前缀块贡献，于是可以计算一个元素与一段连续块的贡献。

结合上面的其他预处理，可以获得10分。

其实上面的预处理需要开很多\(n\sqrt n\)的数组，合理寻址优化是通过这题的关键。

结合上面的算法，或许可以获得满分。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #define fo(i,j,k) for(int i=j;i<=k;++i)#define fd(i,j,k) for(int i=j;i>=k;--i)using namespace std;typedef unsigned long long ll;const int N=5e4+10,_N=250;int be[N];struct node{    int l,r;}c[_N];ll a[N];struct node2{    ll x;    int p;}b[N],d[N];ll F[_N][_N],vl[_N][_N];ll f[_N][N],pre[_N][N];ll sum[N][_N];int bz[N];int read(){    char ch=' ';int t=0;    for(;ch<'0' || ch>'9';ch=getchar());    for(;ch>='0' && ch<='9';ch=getchar()) t=(t<<1)+(t<<3)+ch-48;    return t;}ll readll(){    char ch=' ';ll t=0;    for(;ch<'0' || ch>'9';ch=getchar());    for(;ch>='0' && ch<='9';ch=getchar()) t=(t<<1)+(t<<3)+ch-48;    return t;}bool cmp(node2 x,node2 y){    return x.x
        
         c[j].l && b[p-1].x>a[u]) p--,s1+=b[p].p,s2+=b[p].x,s3+=b[p].p*b[p].x;                vl[j][i]+=a[u]*s1+s2*u-s3-a[u]*u*(ll)(c[j].r-p+1);            }        }    }    fo(l,2,tt)    fo(i,1,tt-l+1){        int j=i+l-1;        F[i][j]=F[i][j-1]+F[i+1][j]-F[i+1][j-1]+vl[i][j];    }    fo(i,1,n-1) f[1][i]=(ll)abs((int)a[i]-(int)a[i+1]);    fo(j,2,_n)    fo(i,1,n-j) f[j][i]=f[j-1][i]+f[j-1][i+1]-f[j-2][i+1]+(ll)abs((int)a[i]-(int)a[i+j])*j;    sort(d+1,d+n+1,cmp);    fo(i,1,tt){        int p=c[i].l-1;        ll s1=0,s2=0,s3=0;        fo(j,1,n){            int k=d[j].p;            if(be[k]==i) continue;            while(p
         
          c[i].l && b[p-1].x>a[k]) p--,s1+=b[p].p,s2+=b[p].x,s3+=b[p].p*b[p].x; pre[i][j]+=(a[k]*s1+k*s2-s3-a[k]*k*(c[i].r-p+1))*(p
          
           l1 && b[p-1].x>a[k]) if(bz[b[--p].p]==z) t++,s1+=b[p].p,s2+=b[p].x,s3+=b[p].p*b[p].x; ans+=a[k]*s1+k*s2-s3-a[k]*k*t; } printf("%llu\n",ans); }}