【BZOJ 3509】[CodeChef] COUNTARI

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3509
原题传送门:https://www.codechef.com/problems/COUNTARI
神犇题解:http://blog.miskcoo.com/2015/04/bzoj-3509

解题报告

这题如果没有$i<j<k$那么撸一发FFT就可以了
现在考虑$i<j<k$的限制,我们可以分块!

设块的大小为$S$,那么对于$j,k$或$i,j$在同一个块内的,我们可以$O(S^2)$暴力
对于$i,k$都不与$j$在同一个块的情况,我们可以用FFT做到$O(\frac{n}{S} \cdot v \log v)$
然后复杂度分析要准确的话应该搞倒数,但我不会QwQ

XeHoTh似乎用一份巨强暴力,卡到了BZOJ和CC的Rank 1
伏地膜啊!太强大了 _(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 70009;
const int N = 100009;
const int T = 15;
const int L = 1 << T + 1;
const double EPS = 0.5;
const double PI = acos(-1);
 
int n,S,ed,arr[N],tot[M],pos[M];
struct COMPLEX{
	double a,b;
	inline COMPLEX() {}
	inline COMPLEX(double x, double y):a(x),b(y) {}
	inline COMPLEX operator - (const COMPLEX &B) {return COMPLEX(a-B.a,b-B.b);}
	inline COMPLEX operator + (const COMPLEX &B) {return COMPLEX(a+B.a,b+B.b);}
	inline COMPLEX operator * (const COMPLEX &B) {return COMPLEX(a*B.a-b*B.b,a*B.b+b*B.a);}
}a1[M],a2[M],bas(1,0);
LL vout,cnt[M];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void FFT(COMPLEX *a, int T = 1) {
    for (int i=0;i<L;i++) if (pos[i]<i) swap(a[pos[i]],a[i]);
    for (int l=2;l<=L;l<<=1) {
        COMPLEX wn(cos(2*PI/l),sin(2*PI/l)*T),w(1,0);
        for (int i=0;i<L;i+=l,w=bas) {
            for (int j=i;j<(i+(l>>1));j++,w=w*wn) {
                COMPLEX tmp = w * a[j+(l>>1)];
                a[j+(l>>1)] = a[j] - tmp;
                a[j] = a[j] + tmp;
            }
        }
    }   
}
 
int main() {
    n = read(); S = 4000;
    for (int i=1;i<=n;i++) arr[i] = read();
    for (int i=1;i<L;i++) pos[i] = (pos[i>>1]>>1)|((i&1)<<T);
    for (int i=S+1;i+S<=n;i+=S) { 
        memset(a1,0,sizeof(a1));
        memset(a2,0,sizeof(a2));
        for (int j=1;j<i;j++) a1[arr[j]] = a1[arr[j]] + bas;
        for (int j=i+S;j<=n;j++) a2[arr[j]] = a2[arr[j]] + bas;
        FFT(a1); FFT(a2);
        for (int j=0;j<L;j++) a1[j] = a1[j] * a2[j];
        FFT(a1, -1);
        for (int j=0;j<L;j++) cnt[j] = a1[j].a / L + EPS;
        for (int j=i;j<i+S;j++) vout += cnt[arr[j]<<1];
    }
    for (int i=1,t;i<=n;i+=S) {
        ed = max(ed, i);
        for (int j=i,lim=min(n+1,i+S);j<lim;j++) {
            for (int k=j+1;k<lim;k++) {
                t = (arr[j] << 1) - arr[k];
                vout += t<M&&t>0? tot[t]: 0;
            }
            tot[arr[j]]++;
        }
    }
    memset(tot,0,sizeof(tot));
    for (int i=ed,t;i>0;i-=S) {
        for (int j=min(n,i+S-1);j>=i;j--) {
            for (int k=j-1;k>=i;k--) {
                t = (arr[j] << 1) - arr[k];
                vout += t<M&&t>0? tot[t]: 0;
            }
        }
        for (int j=min(n,i+S-1);j>=i;j--) tot[arr[j]]++;
    } 
    printf("%lld\n",vout);
    return 0;
}

2 thoughts to “【BZOJ 3509】[CodeChef] COUNTARI”

  1. I’m still learning from you, as I’m making my way to the top as well. I definitely enjoy reading all that is written on your blog.Keep the aarticles coming. I enjoyed it!

Leave a Reply to Maryln Sulecki Cancel reply

Your email address will not be published. Required fields are marked *