Pro：
https://codeforces.com/gym/102028/problem/H
Sol：
用(SAM)枚举不同子串后
问题转换为下面这个形式
(q)组询问
每次询问包含(l,r,x)三个参数，求下式
[sum_{i=l}^r max(i,x)
]
这个东西是个套路题
离线+线段树+单调栈即可
#include<bits/stdc++.h>
#define N 1100000
#define db double
#define ll long long
#define ldb long double
#define ull unsigned long long
using namespace std;
const ll h=3,ki=149,mo=998244353;
ll mod(ll x){return (x%mo+mo)%mo;}
ll inc(ll x,ll k){x+=k;return x<mo?x:x-mo;}
ll dec(ll x,ll k){x-=k;return x>=0?x:x+mo;}
ll ksm(ll x,ll k)
{
ll ans=1;
while(k){if(k&1)ans=1ll*ans*x%mo;k>>=1;x=1ll*x*x%mo;}
return mod(ans);
}
ll inv(ll x){return ksm(x,mo-2);}
ll read()
{
char ch=0;ll x=0,flag=1;
while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0',ch=getchar();}
return x*flag;
}
void write(ll x)
{
if(!x)return (void)putchar(48);
if(x<0)putchar(45),x=-x;
ll len=0,p[20];
while(x)p[++len]=x%10,x/=10;
for(ll i=len;i>=1;i--)putchar(p[i]+48);
}
const db eps=1e-7,inf=1e9+7,pi=acos(-1);
db Read(){db x;scanf("%lf",&x);return x;}
void Write(db x){printf("%lf",x);}
ll n,cnt,root,size,last,a[N];
struct node
{
ll pos,len,lnk;
map<ll,ll>nxt;
}s[N];
void insert(ll k)
{
ll cur=++size,p=last;last=cur;
s[cur].pos=s[cur].len=s[p].len+1;
while(p&&!s[p].nxt[k])s[p].nxt[k]=cur,p=s[p].lnk;
if(!p){s[cur].lnk=root;return;}
ll q=s[p].nxt[k];
if(s[p].len+1==s[q].len)s[cur].lnk=q;
else
{
ll clone=++size;
s[clone]=s[q];s[clone].len=s[p].len+1;
while(p&&s[p].nxt[k]==q)s[p].nxt[k]=clone,p=s[p].lnk;
s[q].lnk=s[cur].lnk=clone;
}
}
struct query{ll x,l,r;}p[N];
bool cmp(query a,query b){return a.x<b.x;}
struct Segment_Tree
{
#define lson o<<1
#define rson o<<1|1
#define mid ((l+r)>>1)
ll sumv[N*4],addv[N*4];
void pushup(ll o)
{
sumv[o]=sumv[lson]+sumv[rson];
}
void pushdown(ll o,ll l,ll r)
{
addv[lson]+=addv[o];
addv[rson]+=addv[o];
sumv[lson]+=(mid-l+1)*addv[o];
sumv[rson]+=(r-mid)*addv[o];
addv[o]=0;
}
void build(ll o,ll l,ll r)
{
sumv[o]=addv[o]=0;
if(l==r)return;
build(lson,l,mid);build(rson,mid+1,r);
}
void optadd(ll o,ll l,ll r,ll ql,ll qr,ll k)
{
if(ql<=l&&r<=qr)
{
addv[o]+=k;
sumv[o]+=(r-l+1)*k;
return;
}
pushdown(o,l,r);
if(ql<=mid)optadd(lson,l,mid,ql,qr,k);
if(qr>mid)optadd(rson,mid+1,r,ql,qr,k);
pushup(o);
}
ll query(ll o,ll l,ll r,ll ql,ll qr)
{
if(ql<=l&&r<=qr)return sumv[o];
pushdown(o,l,r);
ll ans=0;
if(ql<=mid)ans+=query(lson,l,mid,ql,qr);
if(qr>mid)ans+=query(rson,mid+1,r,ql,qr);
return ans;
}
}T;
struct Monotonoue_stack
{
ll s[N],L,R;
void clear(){L=1;R=0;}
void insert(ll x)
{
while(L<=R&&a[s[R]]<=a[x])T.optadd(1,1,n,s[R-1]+1,s[R],a[x]-a[s[R]]),R--;
s[++R]=x;T.optadd(1,1,n,x,x,a[x]);
}
}st;
void work()
{
n=read();cnt=0;root=size=last=1;
for(ll i=1;i<=n;i++)a[i]=read(),insert(a[i]);
for(ll x=2;x<=size;x++)
{
ll t=s[x].pos,l=s[s[x].lnk].len+1,r=s[x].len;
p[++cnt]={t,t-r+1,t-l+1};
}
ll res=0;
sort(p+1,p+cnt+1,cmp);
st.clear();T.build(1,1,n);
for(ll i=1,j=0;i<=n;i++)
{
st.insert(i);
while(j<cnt&&p[j+1].x==i)j++,res+=T.query(1,1,n,p[j].l,p[j].r);
}
printf("%lld
",res);
for(ll x=1;x<=size;x++)s[x].pos=s[x].len=s[x].lnk=0,s[x].nxt.clear();
}
int main()
{
ll t=read();
for(ll i=1;i<=t;i++)work();
return 0;
}