相关链接
题目传送门: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; }
Hey there, You’ve done an excellent job. I’ll definitely digg it and personally suggest to my friends. I am sure they will be benefited from this site.
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!