1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <bits/stdc++.h>
using namespace std;
const int N=400010;
int T,n,a[N],fail[N],len[N],idx,ps[N],tmp[N],rt;
using ll=long long;
map<int,int>son[N];
int extend(int rt,int c){
int p=rt,cur=++idx;
len[cur]=len[rt]+1;
while(~p&&!son[p].count(c))son[p][c]=cur,p=fail[p];
if(~p){
int q=son[p][c];
if(len[p]+1==len[q])fail[cur]=q;
else{
int cl=++idx;
fail[cl]=fail[q],len[cl]=len[p]+1;
son[cl]=son[q];
while(~p&&son[p][c]==q)son[p][c]=cl,p=fail[p];
fail[cur]=fail[q]=cl;
}
}
return cur;
}
ll ans=0;
using pii=pair<int,int>;
vector<pii>v[N];
int L[N],s[N],top;
ll C[N<<2],tag[N<<2];
void build(int p,int l,int r){
C[p]=tag[p]=0;
if(l==r)return ;
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pls(int p,ll x,int sz){C[p]=x*sz,tag[p]=x;}
void down(int p,int l,int r){
if(!tag[p])return ;
int mid=(l+r)>>1;
pls(p<<1,tag[p],mid-l+1);
pls(p<<1|1,tag[p],r-mid);
tag[p]=0;
}
void insert(int p,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr)return pls(p,x,r-l+1);
int mid=(l+r)>>1;
down(p,l,r);
if(mid>=ql)insert(p<<1,l,mid,ql,qr,x);
if(mid<qr)insert(p<<1|1,mid+1,r,ql,qr,x);
C[p]=C[p<<1]+C[p<<1|1];
}
ll query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return C[p];
int mid=(l+r)>>1;
down(p,l,r);
ll res=0;
if(mid>=ql)res+=query(p<<1,l,mid,ql,qr);
if(mid<qr)res+=query(p<<1|1,mid+1,r,ql,qr);
return res;
}
namespace FastIO{
char buf[1<<20],*p1,*p2;
char getchar(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++;}
template<class T> void read(T &x){
x=0;
char c=getchar();
while(c<48||c>57)c=getchar();
while(c>=48&&c<=57)
x=x*10+(c&15),c=getchar();
}
template<class T,class ...Args> void read(T &x,Args &...args){
read(x);read(args...);
}
}
using FastIO::read;
void WZH(){
read(n);
for(int i=1;i<=n;i++)read(a[i]),v[i].clear();
for(int i=0;i<=idx;i++){
fail[i]=len[i]=ps[i]=0;
son[i].clear();
}
fail[0]=-1;
idx=rt=ans=0;
for(int i=1;i<=n;i++)rt=extend(rt,a[i]),tmp[i]=rt;
for(int i=1;i<=n;i++){
int t=tmp[i];
while(~t&&!ps[t])ps[t]=i,t=fail[t];
}
for(int i=1;i<=idx;i++){
int maxn=len[i],minn=len[fail[i]]+1;
v[ps[i]].push_back({ps[i]-maxn+1,ps[i]-minn+1});
}
for(int i=n;i>=1;i--){
while(top&&a[s[top]]<=a[i])L[s[top]]=i+1,--top;
s[++top]=i;
}
while(top)L[s[top]]=1,top--;
build(1,1,n);
for(int i=1;i<=n;i++){
insert(1,1,n,L[i],i,a[i]);
for(pii j:v[i])
ans+=query(1,1,n,j.first,j.second);
}
printf("%lld\n",ans);
}
int main(){
read(T);
while(T--)WZH();
return 0;
}
|
