Nikita and Order Statistics(FFT)

描述

传送门:Codeforces Round #488 by NEAR (Div. 1) - Problem E

Nikita likes tasks on order statistics, for example, he can easily find the k-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are such that a given number $x$ is the $k$-th number in increasing order on this segment. In other words, you should find the number of segments of a given array such that there are exactly $k$ numbers of this segment which are less than $x$.

Nikita wants to get answer for this question for each k from $0$ to $n$, where $n$ is the size of the array.

Input

The first line contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5, -10^9 \le x \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the given array.

Output

Print $n + 1$ integers, where the $i$-th number is the answer for Nikita’s question for $k = i - 1$.

Example

Input Output
1
2
5 3
1 2 3 4 5
1
6 5 4 0 0 0
1
2
2 6
-5 9
1
1 2 0
1
2
6 99
-1 -1 -1 -1 -1 -1
1
0 6 5 4 3 2 1

思路

  • 首先考虑前缀子段中小于$x$的数的个数,记作$p[i]$。
  • 对$p[i]$计数,记作$r$。那么$ans[d] = \sum\limits_{j - i = d} r[i] * r[j]$
  • 适当变换一下,令$v[i] = r[n - i]$,则$$ans[d] = \sum\limits_{i + j = n + d} r[i] * v[j]$$
  • 然后上面这个式子就可以用FFT来求了。
  • 当然$k = 0$的时候需要去重和去序。
  • 数据范围告诉我们答案最大会到$10 ^ {10}$,所以要使用long long

为了防止精度问题,官方题解中给出的方法是:选择两个质数分别做NTT之后,用中国剩余定理求解。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

namespace FFT
{
const double PI = acos(-1.0);
struct Complex
{
double x, y;
Complex(double x = 0.0, double y = 0.0) { this->x = x, this->y = y; }
Complex operator-(const Complex& b) const { return Complex(x - b.x, y - b.y); }
Complex operator+(const Complex& b) const { return Complex(x + b.x, y + b.y); }
Complex operator*(const Complex& b) const { return Complex(x * b.x - y * b.y, x * b.y + y * b.x); }
};

void fft(vector<Complex>& y, int len, int on)
{
for (int i = 1, j = len / 2; i < len - 1; i++)
{
if (i < j) swap(y[i], y[j]);
int k = len / 2;
while (j >= k) j -= k, k /= 2;
if (j < k) j += k;
}
for (int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
for (int j = 0; j < len; j += h)
{
Complex w(1, 0);
for (int k = j; k < j + h / 2; k++)
{
Complex u = y[k];
Complex t = w * y[k + h / 2];
y[k] = u + t, y[k + h / 2] = u - t;
w = w * wn;
}
}
}
if (on == -1)
for (int i = 0; i < len; i++) y[i].x /= len;
}
template <class T>
vector<T> multiply(vector<T>& a, vector<T>& b)
{
int n = a.size() + b.size() - 1;
int len = 1;
while (len < n) len <<= 1;
vector<Complex> aa(len), bb(len);
vector<T> ret(n);
for (int i = 0; i < a.size(); i++) aa[i] = a[i];
for (int i = 0; i < b.size(); i++) bb[i] = b[i];
fft(aa, len, 1), fft(bb, len, 1);
for (int i = 0; i < len; i++) aa[i] = aa[i] * bb[i];
fft(aa, len, -1);
for (int i = 0; i < n; i++) ret[i] = (T)(aa[i].x + 0.5);
return ret;
}
}; // namespace FFT

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, x;
scanf("%d%d", &n, &x);
vector<int> a(n + 1), pre(n + 1);
for (int i = 1, s; i <= n; i++)
{
scanf("%d", &s);
a[i] = s < x;
}
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
vector<ll> aa(n + 1), bb(n + 1);
for (int i = 0; i <= n; i++) aa[pre[i]]++;
for (int i = 0; i <= n; i++) bb[n - pre[i]]++;
auto ans = FFT::multiply(aa, bb);
ans[n] -= (n + 1);
ans[n] >>= 1;
for (int i = n; i <= n * 2; i++)printf("%lld ", ans[i]);
return 0;
}
捐助作者
0%