题目链接

CF993E

题解

我们记小于\(x\)的位置为\(1\)，否则为\(0\)

区间由端点决定，转为两点前缀和相减

我们统计出每一种前缀和个数，记为\(A[i]\)表示值为\(i\)的位置出现的次数

那么对于\(k > 0\)有

令

那么有

就成了卷积的形式

第\(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;

}