题目链接
题解
我们记小于(x)的位置为(1)，否则为(0)
区间由端点决定，转为两点前缀和相减
我们统计出每一种前缀和个数，记为(A[i])表示值为(i)的位置出现的次数
那么对于(k > 0)有
[ans_k = sumlimits_{x - y = k} A[x]A[y]
]
令
[B[x] = A[n - x]
]
那么有
[ans_k = sumlimits_{x + y = n + k} A[x]B[y]
]
就成了卷积的形式
第(n + k)项系数就是(ans_k qquad k > 0)
对于(k = 0)，可以直接统计，也可以减去卷积中重复的部分
首先减去空串的个数(n + 1)，然后再除以(2)【因为当(x)和(y)相等，大小顺序就可以颠倒了】
最后求得的就是(k = 0)的答案
复杂度(O(nlogn))
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 800005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
return flag ? out : -out;
}
struct E{
double a,b;
E(){}
E(double x,double y):a(x),b(y) {}
E(int x,int y):a(x),b(y) {}
inline E operator =(const int& b){
this->a = b; this->b = 0;
return *this;
}
inline E operator =(const double& b){
this->a = b; this->b = 0;
return *this;
}
inline E operator /=(const double& b){
this->a /= b; this->b /= b;
return *this;
}
};
inline E operator *(const E& a,const E& b){
return E(a.a * b.a - a.b * b.b,a.a * b.b + a.b * b.a);
}
inline E operator *=(E& a,const E& b){
return a = E(a.a * b.a - a.b * b.b,a.a * b.b + a.b * b.a);
}
inline E operator +(const E& a,const E& b){
return E(a.a + b.a,a.b + b.b);
}
inline E operator -(const E& a,const E& b){
return E(a.a - b.a,a.b - b.b);
}
const double pi = acos(-1);
int R[maxn];
void fft(E* a,int n,int f){
for (int i = 0; i < n; i++) if (i < R[i]) swap(a[i],a[R[i]]);
for (int i = 1; i < n; i <<= 1){
E wn(cos(pi / i),f * sin(pi / i));
for (int j = 0; j < n; j += (i << 1)){
E w(1,0),x,y;
for (int k = 0; k < i; k++,w = w * wn){
x = a[j + k],y = w * a[j + k + i];
a[j + k] = x + y; a[j + k + i] = x - y;
}
}
}
if (f == -1) for (int i = 0; i < n; i++) a[i] /= n;
}
E A[maxn],B[maxn];
int cnt[maxn],N,x,a[maxn];
int main(){
N = read(); x = read();
cnt[0]++;
REP(i,N) cnt[a[i] = a[i - 1] + (read() < x ? 1 : 0)]++;
for (int i = 0; i <= N; i++) A[i] = cnt[i],B[i] = cnt[N - i];
int n = 1,L = 0;
while (n <= (N << 1)) n <<= 1,L++;
for (int i = 1; i < n; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
fft(A,n,1); fft(B,n,1);
for (int i = 0; i < n; i++) A[i] *= B[i];
fft(A,n,-1);
A[N].a -= N + 1; A[N].a /= 2;
for (int i = 0; i <= N; i++)
printf("%.0lf ",floor(A[N + i].a + 0.3));
return 0;
}