题意：统计满足\(i<j<k, 2*a[j] = a[i] + a[k]\)的个数

---

\(2*a[j]\)不太好处理，暴力fft不如直接暴力

考虑分块

每个块用生成函数统计j在块中ik在两边的块中的

有两个在块中或者三个都在暴力统计，实时维护两边权值出现次数

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N = (1<<16) + 5, M = 1e5+5;const double PI = acos(-1.0);inline int read() { char c=getchar(); int x=0,f=1; while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f;}struct meow{ double x, y; meow(double a=0, double b=0):x(a), y(b){}};meow operator +(meow a, meow b) {return meow(a.x+b.x, a.y+b.y);}meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}meow conj(meow a) {return meow(a.x, -a.y);}typedef meow cd;namespace fft { int n, rev[N]; cd omega[N], omegaInv[N]; void init(int lim) { n = 1; while(n < lim) n <<= 1; for(int i=0; i
          
           >1]>>1) | ((i&1)<<(k-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int l=2; l<=n; l<<=1) { int m = l>>1; for(cd *p = a; p != a+n; p += l) for(int k=0; k
           
            = 0) ans += c2[t]; t = (a[i]<<1) - a[j]; if(t >= 0) ans += c1[t]; } c1[a[i]]++; } //printf("hi [%d, %d] %lld\n", l, r, ans); } for(int l=1; l<=n; l+=block) { //printf("l %d\n", l); int r = min(n, l+block-1); memset(p, 0, sizeof(p)); memset(q, 0, sizeof(q)); for(int i=1; i