【BZOJ4199】[Noi2015]品酒大会

题面：

题解：听说能用SAM？SA默默水过~

本题的实现还是非常简单的，先求出height数组，然后两杯酒'r'相似就等价于二者中间的height都>=r，于是我们将height排序，从大到小扔进去，那么所有连续的区间中的点对就都是相似的了。维护连续区间可以用并查集。统计点对个数需要维护size，统计最大乘积需要维护最（次）大（小）值，然后没了~

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=300010;int n,m;typedef long long ll;int sa[maxn],st[maxn],ra[maxn],rb[maxn],r[maxn],h[maxn],rank[maxn];int f[maxn],q[maxn],v[maxn];ll ans[maxn],sum[maxn],m1[maxn],m2[maxn],n1[maxn],n2[maxn],siz[maxn];char str[maxn];void work(){	int i,j,p,k,*x=ra,*y=rb;	for(i=0;i
         
          =0;i--)	sa[--st[x[i]]]=i;	for(j=p=1;p
          
           <<=1,m=p) { for(p=0,i=n-j;i
           
            =j) y[p++]=sa[i]-j; for(i=0;i
            
             =0;i--) sa[--st[x[y[i]]]]=y[i]; for(swap(x,y),x[sa[0]]=0,i=p=1;i
             
              h[b];}int main(){ scanf("%d%s",&n,str); int i,j,a,b; for(i=0;i
              
               =0;j--) { ans[j]=ans[j+1],sum[j]=sum[j+1]; for(;h[q[i]]==j&&i<=n;i++) { a=find(q[i]-1),b=find(q[i]); if(m1[a]>m1[b]) m2[b]=max(m1[b],m2[a]),m1[b]=m1[a]; else m2[b]=max(m2[b],m1[a]); if(n1[a]