题面

Description

给定一个长度为N的数组A[]，求有多少对i, j, k（1<=i<j<k<=N）满足A[k]-A[j]=A[j]-A[i]。

Input

第一行一个整数N（N<=10^5）。

接下来一行N个数A[i]（A[i]<=30000）。

Output

一行一个整数。

Sample Input

10

3 5 3 6 3 4 10 4 5 2

Sample Output

9

解题思路

　　比较有意思的一道题。首先直接的思路就是对于一个点来说，把它两边卷起来算贡献，但这样复杂度是\(O(n^2logn)\)的，无法接受。考虑分块，我们其实可以把原序列分块，然后每次\(fft\)块两边，这样算出来的贡献块内都可以用。对于块内的贡献可以直接暴力预处理出，预处理就是用两个数组，一个表示左边一个表示右边，然后先枚举块，再枚举两重块内元素。设块的大小为\(T\)，那么就有\(n/T\)块，时间复杂度为\(O(n*T+\dfrac{n}{T}*\sqrt{n*logn})\)，然后两边平衡一下发现\(T\)取\(\sqrt{nlogn}\)时最优。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN = 100005;const double Pi = acos(-1);typedef long long LL;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x;}int n,a[MAXN],bl[MAXN],l[MAXN],r[MAXN];int siz,num,rev[MAXN<<2],limit=1,mx;int L[30005],R[30005];LL ans;struct Complex{ double x,y; Complex(double xx=0,double yy=0){ x=xx;y=yy; }}f[30005<<2],g[30005<<2];Complex operator+(const Complex A,const Complex B){return Complex(A.x+B.x,A.y+B.y);}Complex operator-(const Complex A,const Complex B){return Complex(A.x-B.x,A.y-B.y);}Complex operator*(const Complex A,const Complex B){return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}inline void fft(Complex *f,int type){ for(int i=0;i
          
           >1;Wn=Complex(cos(Pi/len),type*sin(Pi/len)); for(int k=0;k
           
            y?x:y;}signed main(){ n=rd();siz=sqrt(n*log2(n))+1;num=n/siz;if(n%siz) siz++; for(int i=1;i<=n;i++) {a[i]=rd();bl[i]=(i-1)/siz+1;R[a[i]]++;} for(int i=1;i<=num;i++) l[i]=(i-1)*siz+1,r[i]=i*siz;r[num]=n;int tmp; for(int i=1;i<=num;i++){ for(int j=l[i];j<=r[i];j++) R[a[j]]--; for(int j=l[i];j<=r[i];j++){ for(int k=j+1;k<=r[i];k++){ tmp=a[j]*2-a[k]; if(tmp>=0 && tmp<=30000) ans+=L[tmp]; tmp=a[k]*2-a[j]; if(tmp>=0 && tmp<=30000) ans+=R[tmp]; } L[a[j]]++; } }memset(L,0,sizeof(L)); for(int i=2;i
            
             >1]>>1)|((j&1)?limit>>1:0); fft(f,1);fft(g,1);for(int j=0;j