【2019icpc焦作H】【后缀数组】求所有 子区间的最大值的和，要求相同的子区间只能算一次

题意：

给出n个数，定义 f [ l, r ]表示 区间 [ l , r ]的最大值，求所有 子区间的最大值的和，要求相同的子区间只能算一次

比如 数列 5 6 5 6 ， 区间 [ 1, 2 ] 和 [ 3, 4]是一模一样的，所以只能算一次。

#include
#define N 200010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define P 998244353
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
 
int a[N],len[N],lg[N];
LL w[N];
int sa[N],t[N],t2[N],c[N],n;
int rak[N],height[N];
 
void build_sa(int m,int *s)
{
    int i,*x=t,*y=t2;
    for (i=0;i=0;i--)sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (i=n-k;i=k)y[p++]=sa[i]-k;
        for (i=0;i=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for (i=1;i=n) break;
        m=p;
    }
}
 
void getheight()
{
    int i,j,k=0;
    for (i=0;ist; st.push(n+1);
 
        for (int i=n;i>0;i--)		//单调栈求右边第一个大于的数的位置
        {
        	while(a[i]>=a[st.top()]) st.pop();
        	len[i]=g[0][i]=st.top();
        	st.push(i);
        }
 
        g[0][n+1]=n+1;
        for (int j=1;(1<0;i--) 	//i为左端点的所有区间最大值的和
        	w[i]=(LL)q[a[i]]*(len[i]-i)+w[len[i]];
 
        for (int i=1;i<=n;i++) a[i-1]=a[i]; a[n++]=0;
 
        build_sa(cnt+2,a);
    	
        getheight();
    
        LL ans=0;
       
        for (int i=1;i=0;j--)		//确定在LCP最靠左的位置--st
                if (g[j][st]<=la) st=g[j][st];
 
            ans+=(LL) q[a[st-1]]*(g[0][st]-la-1)+w[g[0][st]];//两部分相加
        }
        printf("%I64d\n",ans);
    }
    return 0;
}
 
/*
1
6
1 1 1 2 1 2
*/