题意：

　　给你一个数组a1~an，对于k=0~n，求出有多少个数组上的区间满足：区间内恰好有k个数比x小。x为一个给定的数。n<=10^5。值域没有意义。

 

分析：

　　大神们都说这道题是一个套路题，真是长见识%%%。

　　首先我们可以将题面转化，因为x是预先给出的，所以我们可以对其进行预处理，将数列中小于x的数都设为1，其他都为0，然后求一个前缀和，另前缀和数组为s[i]我们开一个数组v[i]，记录在前缀和数组中数值i出现的次数。

　　然后我们可以得到这样一个式子

　　（据说看到这个式子就是套路了）

　　然后我们对这个式子进行一个转化。

　　转化：

　　之后，我们就可以修改上面的式子，变成这样，

　　有些经验的选手可以看得出，这个形式就是一个卷积的形式。

　　所以我们就直接把v数组和t数组看成多项式，用fft做一遍卷积，之后n+k次项的系数就是ans_k

　　k=0时需要特殊处理一下，要去除空串的影响，并且当k=0是，由于i和j的顺序问题，所以每种情况都统计了两次，最后要除以2。

代码：

1 #include
      
        2 #include
       
         3 #define db double 4 #define ll long long 5 #define cp complex
        
          6 using namespace std; 7 const int N=1000005; 8 const db pi=acos(-1); 9 int m,l,r[N],cnt[N],s[N],x;10 cp a[N],b[N],omg[N],inv[N];ll n,ans[N];11 void init(){12     for(int i=0;i
         
          >j)&1) t|=(1<<(lm-j-1));20         if(i
          
           >1ll;39     printf("%lld",ans[0]);40     for(int i=1;i<=q;i++)41     ans[i]=(ll)floor(a[q+i].real()/n+0.5),42     printf(" %lld",ans[i]);puts("");return 0;43 }