傳送門

變一下題目的式子，變成 $A[i]+A[k]=2A[j],i<j,k>j$

發現 $A[i]$ 的值域不大，考慮移動指針 $pos$ 并維護 $cntl[],cntr[]$ 分別表示 $pos$ 左右兩邊各種值的數的數量

設 $ans[i]$ 表示當前 $pos$ 左右兩邊各取一個數，相加為 $i$ 的方案數，那么對于每一個 $j=pos$，貢獻即為 $ans[2A[pos]]$

同時 $ans[i]=\sum_{j=0}^{i}cntl[j]cntr[i-j]$，其實就是一個卷積的形式，可以用 $FFT$ 優化，但是 $ans$ 會隨著 $pos$ 改變一起改變

如果用 $FFT$ 未免大材小用了，對于每一個位置 $pos$ 我們只想知道 $ans[2A[pos]]$，其他的都無關，$FFT$ 好像只會白白增加復雜度

考慮分塊，設塊大小為 $T$

對于塊內的情況可以直接暴力算，復雜度 $n^2/T$

對于 $i$ 在塊左邊，$j$ 在塊內，$k$ 在塊右邊的情況，直接搞 $FFT$

這樣一次 $FFT$ 可以解決 塊大小的答案，設值域為 $S$，那么這樣復雜度就是 $O(n/TSlog_S)$

發現 $T$ 取 $sqrt(n)$ 時最優，但是因為 $FFT$ 常數大，所以可以適當增大 $T$ 來減少 $FFT$ 的次數

具體看代碼就行，不難看懂

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; typedef double db; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=1e5+7; const db pi=acos(-1.0); struct CP {db x,y;CP (db xx=0,db yy=0) { x=xx,y=yy; }inline CP operator + (const CP &tmp) const {return CP(x+tmp.x,y+tmp.y);}inline CP operator - (const CP &tmp) const {return CP(x-tmp.x,y-tmp.y);}inline CP operator * (const CP &tmp) const {return CP(x*tmp.x-y*tmp.y,x*tmp.y+y*tmp.x);} }A[N],B[N]; int n,p[N],T,d[N],cntl[N],cntr[N]; ll ans; void FFT(CP *A,int len,int type) {for(int i=0;i<len;i++) if(i<p[i]) swap(A[i],A[p[i]]);for(int mid=1;mid<len;mid<<=1){CP wn(cos(pi/mid),type*sin(pi/mid));for(int R=mid<<1,j=0;j<len;j+=R){CP w(1,0);for(int k=0;k<mid;k++,w=w*wn){CP x=A[j+k],y=w*A[j+mid+k];A[j+k]=x+y;A[j+mid+k]=x-y;}}} } int main() {n=read(); T=min(n,6*(int)sqrt(n));for(int i=1;i<=n;i++) d[i]=read(),cntr[d[i]]++;for(int i=1;i<n;i+=T){int r=min(i+T-1,n);for(int j=i;j<=r;j++) cntr[d[j]]--;for(int j=i;j<=r;j++){for(int k=j+1;k<=r;k++){int t=(d[j]<<1)-d[k]; if(t>=0) ans+=cntl[t];t=(d[k]<<1)-d[j]; if(t>=0) ans+=cntr[t];}cntl[d[j]]++;}}for(int i=1;i<n;i+=T){int mx=0,r=min(i+T-1,n);for(int j=1;j<i;j++) A[d[j]].x++,mx=max(mx,d[j]);for(int j=r+1;j<=n;j++) B[d[j]].x++,mx=max(mx,d[j]);int len=1,tot=0;while(len<=mx*2) len<<=1,tot++;for(int j=0;j<len;j++) p[j]=(p[j>>1]>>1) | ((j&1)<<(tot-1));FFT(A,len,1); FFT(B,len,1);for(int j=0;j<=len;j++) A[j]=A[j]*B[j];FFT(A,len,-1);for(int j=i;j<=r;j++) ans+=ll(A[d[j]<<1].x/len+0.5);for(int j=0;j<=len;j++) A[j]=B[j]=CP(0,0);}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/LLTYYC/p/11254861.html

總結

以上是生活随笔為你收集整理的BZOJ3509. [CodeChef] COUNTARI的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。