题意：

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

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

 

题解：

假如抛开限制，那就是一个经典的算贡献的题目。

要求重复的区间只能算一次，很容易想到 相同的子串，又联想到后缀数组。

后缀数组中height数组表示字典序相邻的两个后缀的LCP，那么显然LCP就是重复的，我们不能算，如图

对于字典序排第K的后缀，其LCP的部分已经在K-1中计算了，所以我们要新算的区间是右端点在红色圈内的区间

这样就保证不会算重了，那么问题是如何快速计算图中右端点在红色圈内的最大值的和

 

先将问题泛化

给定n个数，对于每个位置，如何求出以它为左端点的所有区间的最大值的和，这个问题与上图的区别就是计算了LCP的部分，我们一会再想办法解决

对于数 x ，他的贡献只能是 从右端点是它本身的区间开始，向右延伸，直到大于x，因为右端点在向后，区间最大值就大于x了，不能算x的贡献

上图所示的区间才能算x的贡献

这样，方法就显然了，对于每个数，找到右边第一个大于它的位置y，中间的数字的个数乘上x再加上已经求出y的答案，就是x的答案

右边第一个大于它的位置可以用单调栈解决

问题解决了一半，怎么才能不算LCP的部分呢

先罗列出从左端点开始递增的一部分，为什么？因为只有这些数才产生了贡献

上图中，右端点在3号往右的区间的最大值的和，就等于左端点为3号的所有区间的最大值的和，这个我们刚刚解决了

而图中右端点介于红线与3号之间的部分，他们的最大值是2号

所以，我们只需要求出最靠近LCP的点2号与3号，求可以求解问题了

怎么求呢

我们已经知道每个数向右第一个大于本身的数的位置了，一个一个往右跳是显然不行的，我们可以用二分的思想，先跳一大步，如果超过了LCP，那下一次就从原地跳少点，如果没过，我们先跳过去，下次再跳小一点

这样，在log的时间内就找到在LCP附近最近的数的位置了，所有的问题也都解决了

 

代码：

#include<bits/stdc++.h>
#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<m;i++)c[i]=0;
    for (i=0;i<n;i++)c[x[i]=s[i]]++;
    for (i=1;i<m;i++)c[i]+=c[i-1];
    for (i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (i=n-k;i<n;i++)y[p++]=i;
        for (i=0;i<n;i++)if (sa[i]>=k)y[p++]=sa[i]-k;
        for (i=0;i<m;i++)c[i]=0;
        for (i=0;i<n;i++)c[x[y[i]]]++;
        for (i=0;i<m;i++)c[i]+=c[i-1];
        for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for (i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p>=n) break;
        m=p;
    }
}

void getheight()
{
    int i,j,k=0;
    for (i=0;i<n;i++)rak[sa[i]]=i;
    for (i=0;i<n;i++)
    {
        if (k)k--;
        j=sa[rak[i]-1];
        while (a[i+k]==a[j+k])k++;
        height[rak[i]]=k;
    }
}

int g[19][N];
int q[N];

int main()
{
    for (int i=1;(1<<i)<N;i++) lg[1<<i]=1;
    for (int i=1;i<N;i++) lg[i]+=lg[i-1];
    int T;
    sc(T);
    while(T--)
    {
        sc(n);
        for (int i=1;i<=n;i++) sc(a[i]),q[i]=a[i];
    	sort(q+1,q+n+1);			//离散化
	    int cnt=unique(q+1,q+n+1)-q-1;
	    for (int i=1;i<=n;i++) a[i]=lb(q+1,q+cnt+1,a[i])-q;
	    a[n+1]=INF;
        stack<int>st; 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<<j)<=n+1;j++) 		//向右走2^j步后的位置
            for (int i=1;i<=n+1;i++) g[j][i]=g[j-1][g[j-1][i]];

        w[n]=q[a[n]]; w[n+1]=0;

        for (int i=n-1;i>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<n;i++)
        {
            int h=height[i];

            if(h==0) {ans+=w[sa[i]+1];continue;}

            int la=sa[i]+h;

            int up=lg[n-sa[i]-1],st=sa[i]+1;

            for (int j=up;j>=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
*/