fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct _complex {
  6.   double x, y;
  7.  
  8.   _complex () : x(0.0), y(0.0) {}
  9.   _complex (double _x, double _y) : x(_x), y(_y) {}
  10.  
  11.   const _complex operator + (const _complex &z) {
  12.     return _complex(x + z.x, y + z.y);
  13.   }
  14.  
  15.   const _complex operator - (const _complex &z) {
  16.     return _complex(x - z.x, y - z.y);
  17.   }
  18.  
  19.   const _complex operator * (const _complex &z) {
  20.     return _complex(x * z.x - y * z.y, x * z.y + y * z.x);
  21.   }
  22. };
  23.  
  24. const int LG = 17;
  25. const int B = 2000;
  26. const int N = 200005;
  27. const int L = 1 << 17;
  28. const double PI = acos(-1);
  29.  
  30. int t, n;
  31. _complex f[N];
  32. int a[N], rev[N];
  33. int pref[N], active[N];
  34. _complex power[2][20][N];
  35.  
  36. void process (void) {
  37.   for (int i = 0; i < L; ++i) {
  38.     rev[i] = 0;
  39.     for (int j = 0; j < LG; ++j) {
  40.       if (i & 1 << j) {
  41.         rev[i] |= 1 << (LG - 1 - j);
  42.       }
  43.     }
  44.   }
  45.  
  46.   for (int dir = 0; dir < 2; ++dir) {
  47.     for (int i = 1; i <= LG; ++i) {
  48.       int l = 1 << i;
  49.       double theta = 2 * PI / l * (dir ? -1 : 1);
  50.       _complex base(cos(theta), sin(theta));
  51.       power[dir][i][0] = _complex(1, 0);
  52.       for (int j = 1; j < (l >> 1); ++j) {
  53.         power[dir][i][j] = base * power[dir][i][j - 1];
  54.       }
  55.     }
  56.   }
  57. }
  58.  
  59. void fft (int dir) {
  60.   for (int i = 0; i < L; ++i) {
  61.     if (i < rev[i]) {
  62.       swap(f[i], f[rev[i]]);
  63.     }
  64.   }
  65.  
  66.   for (int i = 1; i <= LG; ++i) {
  67.     int l = 1 << i;
  68.     for (int j = 0; j < L; j += l) {
  69.       _complex z, *w = power[dir][i];
  70.       _complex *u = f + j, *v = f + j + (l >> 1);
  71.       _complex *lim = f + j + (l >> 1);
  72.       while (u != lim) {
  73.         z = *v * *w;
  74.         *v = *u - z;
  75.         *u = *u + z;
  76.         ++u, ++v, ++w;
  77.       }
  78.     }
  79.   }
  80.  
  81.   if (dir == 1) {
  82.     for (int i = 0; i < L; ++i) {
  83.       f[i].x /= L;
  84.       f[i].y /= L;
  85.     }
  86.   }
  87. }
  88.  
  89. void square (void) {
  90.   for (int j = 0; j < L; ++j) {
  91.     f[j] = _complex(pref[j], 0); 
  92.   }
  93.   fft(0);
  94.   for (int j = 0; j < L; ++j) {
  95.     f[j] = f[j] * f[j];
  96.   }
  97.   fft(1);
  98. }
  99.  
  100. int main() {
  101.   process();
  102.  
  103.   scanf("%d", &t);
  104.   while (t--) {
  105.     memset(pref, 0, sizeof pref);
  106.     memset(active, 0, sizeof active);
  107.  
  108.     scanf("%d", &n);
  109.     for (int i = 1; i <= n; ++i) {
  110.       scanf("%d", a + i);
  111.     }
  112.  
  113.     long long ans = 0;
  114.  
  115.     for (int i = 1; i <= n; i += B) {
  116.       int l = i, r = min(n, i + B - 1);
  117.  
  118.       long long inside = 0;
  119.       for (int j = l; j <= r; ++j) {
  120.         for (int k = j + 1; k <= r; ++k) {
  121.           if (a[k] > a[j]) {
  122.             inside += (long long) active[a[k] - a[j]];
  123.             inside += (long long) pref[a[k] - a[j]];
  124.           }
  125.         }
  126.         ++active[a[j]];
  127.       }
  128.       ans += inside;
  129.  
  130.       if (i > 1) {
  131.         square();
  132.         long long outside = 0;
  133.         for (int j = l; j <= r; ++j) {
  134.           long long add = floor(f[a[j]].x + 0.5);
  135.           if (!(a[j] & 1)) add -= pref[a[j] >> 1];
  136.           outside += (add >> 1);
  137.         }
  138.         ans += outside;
  139.       }
  140.  
  141.       for (int j = l; j <= r; ++j) {
  142.         ++pref[a[j]];
  143.         --active[a[j]];
  144.       }
  145.     }
  146.  
  147.     printf("%lld\n", ans);
  148.   }
  149.   return 0;
  150. }
  151.  
  152.  
Success #stdin #stdout 0.03s 147328KB
comments (?)
stdin
copy 
1
6
2 3 3 4 7 11
stdout
copy 
3
https://ideone.com/L5n6Yl
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!