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 }

轉載于:https://www.cnblogs.com/refun/p/10097284.html

總結

以上是生活随笔為你收集整理的CF993E:Nikita and Order Statistics(FFT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。