[bzoj 3509] [CodeChef] COUNTARI - 블록 FFT

데이터 구조 가 엉망 인 것 같은 데?그러나 데이터 범 위 를 자세히 살 펴 보면 Ai < = 30000 은 우리 가 생 성 함수 로 함부로 할 수 있다 는 것 을 의미한다.식 을 Ai + Ak = 2Aj 로 바 꾸 면 j 를 즐겁게 매 거 하여 j 양쪽 의 생 성 함 수 를 기록 하고 볼 륨 을 구하 면 됩 니 다...?털.이렇게 볼 륨 은 O (nVlogV) 의 / / 아래 에 V = max {A} 를 설정 하면 FFT 횟수 를 어떻게 낮 출 수 있 습 니까?블록 을 고려 하 다.B 조각 으로 나 뉘 었 다 고 가정 하면 조각의 크기 는 L 이다.아니면 j 를 매 거 하여 i 가 블록 안에 있 는 상황 을 고려 하면 대응 수의 발생 횟수 를 뚜렷하게 미리 처리 할 수 있다.k. 블록 안에 있 을 때 도 마찬가지 입 니 다.여기에 중복 되 는 것 을 빼 야 한 다 는 것 을 주의해 라.그리고 i, k 는 모두 블록 밖 에 있 으 면 FFT 로 합 니 다.이렇게 시간 복잡 도 는 O (BVlogV + (B + L) V) 다.위의 이 식 이 존재 하기 때문에 블록 을 너무 작 게 설정 해 서 는 안 됩 니 다. 그렇지 않 으 면 B 가 너무 크 고 FFT 횟수 가 증가 하 며 약 2000 정도 차이 가 나 지 않 습 니 다.어떤 방법 으로 FFT 의 상 수 를 약간 최적화 시 켰 다.　　

#include 
using namespace std;
#define rep(i,a,b) for(int i = a , _ = b ; i <= _ ; i ++)
#define per(i,a,b) for(int i = a , _ = b ; i >= _ ; i --)
#define For(i,a,b) for(int i = a , _ = b ; i <  _ ; i ++)

inline int rd() {
    char c = getchar();
    while (!isdigit(c)) c = getchar() ; int x = c - '0';
    while (isdigit(c = getchar())) x = x * 10 + c - '0';
    return x;
}

inline void upmax(int&a , int b) { if (a < b) a = b; }
inline void upmin(int&a , int b) { if (a > b) a = b; }

typedef long long ll;

const int maxn = 110007;
const int maxs = 61007;
const int maxb = 307;
const int len = 1823;

typedef int arr[maxn];
typedef int blk[maxb];
typedef int num[maxs];

arr a , belong , L , R;
blk st , ed;
num cnt[maxb] , cnt_nxt , cnt_pre;

ll ans;

int n , tot , lim;

void input() {
    n = rd();
    rep (i , 1 , n) a[i] = rd() , upmax(lim , a[i]);
}

inline void init_block() {
    rep (i , 1 , n) belong[i] = (i - 1) / len + 1;
    tot = belong[n];
    rep (i , 1 , tot) st[i] = (i - 1) * len + 1 , ed[i] = i * len;
    upmin(ed[tot] , n);
    rep (i , 1 , tot) {
        rep (j , st[i] , ed[i])
            cnt[i][a[j]] ++;
    }
}

const int maxN = 524299;

struct comp {
    long double real , imag;
    comp(long double real = 0 , long double imag = 0):real(real) , imag(imag) { }
    inline friend comp operator+(comp&a , comp&b)
        { return comp(a.real + b.real , a.imag + b.imag); }
    inline friend comp operator-(comp&a , comp&b)
        { return comp(a.real - b.real , a.imag - b.imag); }
    inline friend comp operator*(comp&a , comp&b)
        { return comp(a.real * b.real - a.imag * b.imag , a.imag * b.real + a.real * b.imag); }
    inline friend void swap(comp&a , comp&b)
        { comp c = a ; a = b ; b = c; }
}A[maxN];

int rev[maxN] , N , Nlen;

ll res[maxN];

inline void FFT_clear() {
    memset(A , 0 , sizeof(comp) * N);
}

inline void FFT_init() {
    for (N = 1 , Nlen = 0;N <= lim + lim;N <<= 1 , Nlen ++) ;
    For (i , 1 , N) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << Nlen - 1);
}

const long double ppi = std::acos(-1.0) * 2;

inline void FFT(comp*a , int n , int v) {
    For (i , 0 , n) if (i < rev[i]) swap(a[i] , a[rev[i]]);
    for (int s = 2;s <= n;s <<= 1) {
        comp g(cos(ppi / s) , v * sin(ppi / s));
        for (int k = 0;k < n;k += s) {
            comp w(1 , 0);
            For (j , 0 , s / 2) {
                comp t = a[k + j + s / 2] * w , u = a[k + j];
                a[k + j + s / 2] = u - t , a[k + j] = u + t;
                w = w * g;
            }
        }
    }
    if (v == -1) For (i , 0 , n)
        a[i].real /= n * 4, a[i].imag /= n;
}

inline void GetConv() {
    FFT_clear();
    rep (i , 0 , lim) A[i] = comp(L[i] + R[i] , L[i] - R[i]);
    FFT(A , N , 1);
    For (i , 0 , N) A[i] = A[i] * A[i];
    FFT(A , N , -1);
    for (int i = 0;i <= lim + lim;i += 2) res[i] = (ll) (A[i].real + 0.5);
}

inline void calc(int p) {
    int t = a[p] + a[p];
    int cur = belong[p];
    rep (i , st[cur] , p - 1) if (t >= a[i])
        ans += R[t - a[i]];
    rep (i , p + 1 , ed[cur]) if (t >= a[i]) {
        ans += cnt_pre[t - a[i]];
        ans += L[t - a[i]];
        if (cur == 1) continue;
    }
    if (p <= ed[1] || p >= st[tot]) return;
    ans += res[t];
}

void solve() {
    init_block();
    FFT_init();

    rep (i , 1 , n) R[a[i]] ++;

    rep (i , 1 , tot) {
        memset(cnt_pre , 0 , sizeof(int) * (lim + 1));
        rep (j , st[i] , ed[i]) cnt_nxt[a[j]] ++;
        rep (j , 0 , lim) R[j] -= cnt[i][j];

        if (i != 1 && i != tot)
            GetConv();

        rep (j , st[i] , ed[i]) cnt_nxt[a[j]] -- , calc(j) , cnt_pre[a[j]] ++;

        rep (j , 0 , lim) L[j] += cnt[i][j];
    }

    printf("%lld
" , ans);
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("data.txt" , "r" , stdin);
        freopen("data.out" , "w" , stdout);
    #endif
    input();
    solve();
    return 0;
}