题意：给定$a_{1\cdots n}$，对$1\leq k\leq n$求满足$a_{l\cdots r}$中最大值个数为$k$的$(l,r)$对数

考虑从$[1,n]$开始，每次求当前区间的最大值对答案的贡献并递归处理

设当前区间$[l,r]$内最大值的位置为$p_{1\cdots m}$（为方便处理，设$p_0=l-1,p_{m+1}=r+1$），令$a_i=p_i-p_{i-1},b_i=p_{i+1}-p_i$，那么它对某个$k$的贡献为$\sum\limits_{i=1}^{m-k+1}a_ib_{i+k-1}$，用FFT求

求区间最大值用线段树，找位置用vector+lower_bound，总共递归最多$n$次，又因为每个数只会参加$1$次FFT，所以总时间复杂度是$O(n\log_2n)$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;typedef double du;const du pi=3.141592653589793238462643383;struct complex{	du x,y;	complex(du a=0,du b=0){x=a;y=b;}};complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}int rev[262144],N;complex w[18][262144];void pre(int n){	int i,j,k;	for(N=1,k=0;N
          
           <<=1)k++; for(i=0;i
           
            >1]>>1)|((i&1)<<(k-1)); for(i=2,k=0;i<=N;i<<=1){ for(j=0;j
            
             >1;k++){ t=w[f][k]; if(on==-1)t.y=-t.y; t=t*a[i/2+j+k]; a[i/2+j+k]=a[j+k]-t; a[j+k]=a[j+k]+t; } } f++; } if(on==-1){ for(i=0;i
             
              >1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); mx[x]=max(mx[x<<1],mx[x<<1|1]);}int query(int L,int R,int l,int r,int x){ if(L<=l&&r<=R)return mx[x]; int mid=(l+r)>>1,s=0; if(L<=mid)s=max(s,query(L,R,l,mid,x<<1)); if(mid
              
               <<1|1)); return s;}ll ans[100010];vector
               
                pos[100010];vector
                
                 ::iterator it,en;int tmp[100010],n;complex A[262144],B[262144];void solve(int l,int r){ if(l>r)return; if(l==r){ ans[1]++; return; } int M,i,mx,*t; mx=query(l,r,1,n,1); M=0; en=upper_bound(pos[mx].begin(),pos[mx].end(),r); for(it=lower_bound(pos[mx].begin(),pos[mx].end(),l);it!=en;it++)tmp[++M]=*it; t=new int[M+2]; tmp[0]=l-1; tmp[M+1]=r+1; memcpy(t,tmp,(M+2)<<2); pre(M<<1); memset(A,0,N<<4); memset(B,0,N<<4); for(i=1;i<=M;i++){ A[i-1]=t[i]-t[i-1]; B[M-i]=t[i+1]-t[i]; } fft(A,1); fft(B,1); for(i=0;i