bzoj 3509: [CodeChef] COUNTARI — 分块+FFT

  • 2017-12-29
  • 0
  • 0

 

3509: [CodeChef] COUNTARI

Time Limit: 40 Sec  Memory Limit: 128 MB

Description

给定一个长度为N的数组A[],求有多少对i, j, k(1<=i<j<k<=N)满足A[k]-A[j]=A[j]-A[i]。

Input

第一行一个整数N(N<=10^5)。
接下来一行N个数A[i](A[i]<=30000)。

Output

一行一个整数。

Sample Input

10
3 5 3 6 3 4 10 4 5 2

Sample Output

9

HINT

Source

妙啊,正常暴力思想可以枚举i,k,这样就可以n^2解决

当然我们可以发现这个很像FFT,但是似乎复杂度O(n^2logn)?

那么如何优化

考虑分块,分类讨论

  1. 如果i,j,k在一个块内,就可以直接暴力,复杂度O(块大小*n)
  2. 如果i,j或j,k,仍可以暴力,在块内枚举,预处理前缀信息,复杂度还是O(块大小*n)
  3. 否则就可以FFT,枚举每一块,左面与右面卷积,在中间枚举j,加起来就好了,复杂度O(n^2logn/块大小)

因为FFT有log,所以块大小应该设大一些,,设为2000比较合适?

(不过我常数好大跑的好慢啊qwq

 

评论

还没有任何评论,你来说两句吧