「BZOJ-3509」[CodeChef] COUNTARI

给定N个整数 $A_1,A_2,⋯A_N $,求有多少个三元组 $(i,j,k)$ 满足 $1≤i<j<k≤N$ 且 $A_j−A_i=A_k−A_j $。

链接

bzoj-3509

输入

第一行一个正整数$ N(3≤N≤10^5)$
第二行$ N $个整数 $A1,A2,⋯,AN , 1≤Ai_≤3×10^4$

输出

输出一个整数表示答案。

样例

输入

1
2
10
3 5 3 6 3 4 10 4 5 2

输出

1
9

HINT

【样例解释】
$1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)$
$2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)$
$3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)$
$4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)$
$5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)$
$6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)$
$7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)$
$8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)$
$9 : (i, j, k) = (5, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)$
【数据范围与约定】

对于$20%$的数据, $N≤5000$

对于另外$30%$的数据, $N≤10^5,1≤Ai≤50$

对于所有数据, $N≤10^5,1≤Ai≤3×10^4$

题解

考虑枚举j。我们可以用$pre[t]$表示在前j个数中,$t$这个数出现了多少次,$nxt[t]$表示后$n-j$个数中,$t$这个数出现了多少次。那么答案就是 $\sum_{u+v=2Aj}{pre[u]×nxt[v]}$

很明显这就是一个卷积的形式,可以用$FFT$优化,然而并没有什么用,复杂度为$n*max(Ai)logmax(Ai)$,只能过掉$50$分。

考虑降低$FFT$的次数,可以选择分块,分别考虑三种情况,当$i$和$j$或者$j$和$k$在同一块中的时候可以直接暴力搞,然后都不在同一块的时候就用$FFT$优化。

因为块的大小如果太小,FFT的次数就会增多,所以不能直接选择$sqrt(n)$作为块的大小,大小为$2000$到$4000$都可以。

xehoth似乎用一份复杂度为$n*max(a[i])$的暴力,卡到了BZOJ和CC的Rank 1,然而评测姬的$CPU$似乎并不是很资瓷$CPU$并发,所以还是被卡了40分
(其实是出题人发现有人暴力水过赶紧把时限调小了$1s$)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
inline void R(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-') p = 1;
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch^'0');
ch = getchar();
}
if (p) v = -v;
}
struct E {
double r, i;
E(double r, double i): r(r), i(i) {}
E() {}
};
inline E operator +(const E &a, const E&b) {
return E(a.r + b.r, a.i + b.i);
}
inline E operator - (const E &a, const E &b) {
return E(a.r - b.r, a.i - b.i);
}
inline E operator * (const E &a, const E &b) {
return E(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}
int n;
int a[100005];
E a1[40004 << 1], a2[40004 << 1];
int rev[40004 << 1];
const int L = 16;
const int len = 1 << L;
const int sz = 4000;
const double pi = acos(-1);
inline void fft(E *a, const int &f) {
for (int i = 0; i < len; ++i) {
if (i < rev[i]) {
swap(a[i], a[rev[i]]);
}
}
for (int i = 1; i < len; i <<= 1) {
E wn = E(cos(pi / i), f * sin(pi / i));
for (int j = 0; j < len; j += i << 1) {
E w = E(1, 0);
for (int k = 0; k < i; ++k, w = w * wn) {
E x = a[j + k], y = a[j + k + i] * w;
a[j + k] = x + y;
a[j + k + i] = x - y;
}
}
}
}
int main () {
R(n);
for (int i = 1; i <= n; ++i) {
R(a[i]);
}
for (int i = 0; i < len; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
long long ans = 0;
for (int i = sz + 1; i + sz <= n; i += sz) {
memset(a1, 0, sizeof(a1));
memset(a2, 0, sizeof(a2));
for (int j = 1; j < i; ++j) a1[a[j]] = a1[a[j]] + E(1, 0);
for (int j = i + sz; j <= n; ++j) a2[a[j]] = a2[a[j]] + E(1, 0);
fft(a1, 1), fft(a2, 1);
for (int j = 0; j < len; ++j)a1[j] = a1[j] * a2[j];
fft(a1, -1);
for (int j = i; j < i + sz; ++j)
ans += (long long)(a1[a[j] << 1].r / len + 0.5);
}
int ed = 0;
int temp;
int tot[70004];
memset(tot, 0, sizeof(tot));
for (int i = 1; i <= n; i += sz) {
ed = i;
for (int j = i; j < min(i + sz, n + 1); ++j) {
for (int k = j + 1; k < min(i + sz, n + 1); ++k) {
temp = (a[j] << 1) - a[k];
if (temp <= 70000 && temp > 0) {
ans += tot[temp];
}
}
tot[a[j]]++;
}
}
memset(tot, 0, sizeof(tot));
for (int i = ed; i > 0; i -= sz) {
for (int j = min(i + sz - 1, n); j >= i; --j) {
for (int k = j - 1; k >= i; --k) {
temp = (a[j] << 1) - a[k];
if (temp <= 70000 && temp > 0) {
ans += tot[temp];
}
}
}
for (int j = min(i + sz - 1, n); j >= i; --j)tot[a[j]]++;
}
cout << ans;
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. HINT
  6. 6. 题解
  7. 7. 代码