今天早上本来就想填掉这个坑的。。。

然后还是血淋淋的一片。

心态崩了就去做跳蚤

调着调着跳蚤才发现我st表模版写挂了。。。

满怀希望的去把这题改了。

然后还是血淋淋的一片。

 

今天晚上一怒之下把以前的代码翻出来改st表

wc，A了？A了！。。

--------------------cnm---------------------

这题常规操作st表求LCP

然后单调栈维护区间

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;int n,a[510000],tt[510000];int sa1[510000],sa2[510000],Rank[510000],Rsort[510000];void get_sa(int m){ for(int i=1;i<=n;i++)Rank[i]=a[i]; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[i]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa1[Rsort[Rank[i]]--]=i; int ln=1,p=0; while(p
           
            0)sa2[++k]=sa1[i]-ln; memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=n;i++)Rsort[Rank[sa2[i]]]++; for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1]; for(int i=n;i>=1;i--)sa1[Rsort[Rank[sa2[i]]]--]=sa2[i]; for(int i=1;i<=n;i++)tt[i]=Rank[i]; p=1;Rank[sa1[1]]=1; for(int i=2;i<=n;i++) { if(tt[sa1[i-1]]!=tt[sa1[i]]||tt[sa1[i-1]+ln]!=tt[sa1[i]+ln])p++; Rank[sa1[i]]=p; } ln*=2;m=p; }}LL height[510000];void get_he(){ int j;LL h=0; for(int i=1;i<=n;i++) { j=sa1[Rank[i]-1]; if(h!=0)h--; while(a[i+h]==a[j+h])h++; height[Rank[i]]=h; }}//-------------------sa--------------------int Bin[30],Log[510000];int f[30][510000],s[510000];int LCP(int x,int y){ int k=Log[y-x+1]; return min(f[k][x],f[k][y-Bin[k]+1]);}void get_st(){ Bin[0]=1;for(int i=1;i<=30;i++)Bin[i]=Bin[i-1]*2; Log[1]=0;for(int i=2;i<=n ;i++)Log[i]=Log[i/2]+1; for(int i=1;i<=n;i++)f[0][i]=height[i]; for(int j=1;Bin[j]<=n;j++) for(int i=1;i+Bin[j]-1<=n;i++) f[j][i]=min(f[j-1][i],f[j-1][i+Bin[j-1]]);}//----------------st-------------------------int q[510000];bool cmp(int n1,int n2){ return Rank[n1]
            
             s[i])top--; L[i]=sta[top],sta[++top]=i; } top=1,sta[1]=T; for(int i=T-1;i>=1;i--) { while(top!=0&&s[sta[top]]>=s[i])top--; R[i]=sta[top],sta[++top]=i; } LL ans=0; for(int i=1;i