算法
(FFT) $O(n\log n)$
由于 $x$ 固定,直接把 $a$ 中小于 $x$ 的数设为 $1$,其余数设为 $0$,只需要求有多少个区间的和为 $k$。设 $s$ 为 $a$ 的前缀和,则只需要求有多少个数对 $s_i, s_j$ 满足 $s_j - s_i = k$,或 $s_j - k = s_i$。设 $f_{s_i}$ 为 $s_i$ 的出现次数,则 $k$ 的答案为
$$ \sum_{i = k}^n f_if_{i - k} = \sum_{i = k}^n f_if_{n - (n + k - i)} = \sum_{i + j = n + k}f_i f_{n - j} $$
设 $g_i = f_{n - i}$,求 $f$ 和 $g$ 的卷积即可。
另外,需要特判 $k = 0$,因为不能选长度为 $0$ 的区间。
C++ 代码
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < n; ++i)
using std::cin;
using std::cout;
const int N = 600010;
const double PI = acos(-1);
struct Complex {
double x, y;
Complex operator+ (const Complex& t) const {
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const {
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const {
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
} f[N], g[N];
int s[N];
int rev[N], bit, tot;
int ans[N];
void fft(Complex f[], int inv) {
for (int i = 0; i < tot; ++i) {
if (i < rev[i]) std::swap(f[i], f[rev[i]]);
}
for (int mid = 1; mid < tot; mid <<= 1) {
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
for (int i = 0; i < tot; i += mid * 2) {
auto wk = Complex({1, 0});
for (int j = 0; j < mid; ++j, wk = wk * w1) {
auto x = f[i + j], y = wk * f[i + j + mid];
f[i + j] = x + y, f[i + j + mid] = x - y;
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; ++i) {
int y; cin >> y;
s[i] = s[i - 1] + (int)(y < x);
}
for (int i = 0; i <= n; ++i) f[s[i]].x++;
for (int i = 0; i <= n; ++i) g[i].x = f[n - i - 1].x;
while ((1 << bit) < 2 * n + 1) bit++;
tot = 1 << bit;
for (int i = 0; i < tot; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
fft(f, 1), fft(g, 1);
for (int i = 0; i < tot; ++i) f[i] = f[i] * g[i];
fft(f, -1);
int res = 0, cnt = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] != s[i - 1]) res += (cnt + 1) * cnt / 2, cnt = 0;
else ++cnt;
}
res += (cnt + 1) * cnt / 2;
cout << res << " ";
for (int i = 0; i < n; ++i) cout << (int)(f[i + n].x / tot + 0.5) << " \n"[i == n - 1];
return 0;
}