Description
给你一个数组 $a_{1 sim n}$，对于 $k = 0 sim n$，求出有多少个数组上的区间满足：区间内恰好有 $k$ 个数比 $x$ 小。$x$ 为一个给定的数。
Input
第一行$n,x$。
第二行给出$n$个数Output
一行答案。
Sample Input1
5 3
1 2 3 4 5
Sample Output1
6 5 4 0 0 0
Sample Input2
2 6
-5 9
Sample Output2
1 2 0
Sample Input3
6 99
-1 -1 -1 -1 -1 -1
Sample Output3
0 6 5 4 3 2 1
Solution
为什么这个题网上大部分题解分析来分析去我都看不懂啊……QAQQQ
感觉我的理解能力还是太渣了……
首先我们把小于$x$的置为$1$，否则置为$0$，然后求一个前缀和，并把这些前缀和安排到一个桶里面。
记这个桶为$f[i]$，表示前缀和$=i$的个数。
假设我们枚举$i=0 sim n$，来代表$k$，那么对于一个$i$来说，它的答案就是
$sum_{j=0}^{n}f[j]*f[j+i]$。然后这玩意儿就是套路了，设$g[n-j]=f[j]$，
就成了$sum_{j=0}^{n}g[n-j]*f[j+i]$，$FFT$卷一下就好了。
注意当$k=0$时，会有$n+1$次自己和自己算到一起的情况，减掉这种情况然后再除$2$就好了。
为什么要除$2$因为两个前缀和如果相同的话就会$a$和$b$算一次，$b$和$a$算一次……
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #define N (800009) 5 #define LL long long 6 using namespace std; 7 8 int n,x,fn,l,tmp,r[N],cnt[N],sum[N]; 9 LL ans[N]; 10 11 double pi=acos(-1.0); 12 struct complex 13 { 14 double x,y; 15 complex(double xx=0,double yy=0) 16 { 17 x=xx; y=yy; 18 } 19 }a[N],b[N]; 20 21 complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);} 22 complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);} 23 complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} 24 complex operator / (complex a,double b) {return complex(a.x/b,a.y/b);} 25 26 void FFT(int n,complex *a,int opt) 27 { 28 for (int i=0; i<n; ++i) 29 if (i<r[i]) swap(a[i],a[r[i]]); 30 for (int k=1; k<n; k<<=1) 31 { 32 complex wn=complex(cos(pi/k),opt*sin(pi/k)); 33 for (int i=0; i<n; i+=k<<1) 34 { 35 complex w=complex(1,0); 36 for (int j=0; j<k; ++j,w=w*wn) 37 { 38 complex x=a[i+j],y=w*a[i+j+k]; 39 a[i+j]=x+y; a[i+j+k]=x-y; 40 } 41 } 42 } 43 if (opt==-1) for (int i=0; i<n; ++i) a[i]=a[i]/n; 44 } 45 46 int main() 47 { 48 scanf("%d%d",&n,&x); 49 cnt[0]++; 50 for (int i=1; i<=n; ++i) 51 { 52 scanf("%d",&tmp); 53 sum[i]=sum[i-1]+(tmp<x); cnt[sum[i]]++; 54 } 55 for (int i=0; i<=n; ++i) 56 a[i].x=b[n-i].x=cnt[i]; 57 fn=1; 58 while (fn<=2*n) fn<<=1, l++; 59 for (int i=0; i<fn; ++i) 60 r[i]=(r[i>>1]>>1) | ((i&1)<<(l-1)); 61 FFT(fn,a,1); FFT(fn,b,1); 62 for (int i=0; i<fn; ++i) 63 a[i]=a[i]*b[i]; 64 FFT(fn,a,-1); 65 for (int i=0; i<=n; ++i) 66 ans[i]=(LL)(a[n+i].x+0.5); 67 for (int i=0; i<=n; ++i) 68 printf("%lld ",(i==0)?((ans[i]-n-1)/2):(ans[i])); 69 }