朴素问题是一个算贡献的题目，有很多做法，例如枚举以i为最大值然后二分两边计算每个点的贡献
对于这题，因为遇到了需要去重的问题，已知对于这种去重，就是数组有相等的地方。这样我们可以想到使用后缀数组进行去重
如果采用这种去重的方法，我们算贡献就要换一种方法，我们可以根据后缀数组的形式调整贡献的方法。
因此我们定义以i为左端点的区间所产生的贡献，先用单调栈算出比他大的第一个数，这样可以算两遍求取每个点的区间答案。
考虑去重就是考虑lcp，因为lcp部分已经在前面取到了，因此现在就要考虑右端点在lcp后面的情况，对于这种情况，我们发现需要维护一个最大值，这个用线段树维护即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+10; int a[N]; vector<int> num; int sa[N],rk[N],od[N],cnt[N],id[N],px[N]; int n; int h[N]; stack<int> q; ll sum[N]; int nxt[N]; struct node{ int l,r; int mx; int id; }tr[N<<2]; bool cmp(int x, int y, int w){ return od[x]==od[y]&&od[x+w]==od[y+w]; } void da(int n,int m){ int i; for(i=0;i<=m;i++) cnt[i]=0; for(i=1;i<=n;i++) cnt[rk[i]=a[i]]++; for(i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(i=n;i>=1;i--) sa[cnt[rk[i]]--]=i; int p; for(int w=1;w<n;w<<=1,m=p){ p=0; for(i=n;i>n-w;i--) id[++p]=i; for(i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w; for(i=0;i<=m;i++) cnt[i]=0; for(i=1;i<=n;i++) cnt[px[i]=rk[id[i]]]++; for(i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(i=n;i>=1;i--) sa[cnt[px[i]]--]=id[i]; for(i=0;i<=n;i++) od[i]=rk[i]; for(p=0,i=1;i<=n;i++){ rk[sa[i]]=cmp(sa[i-1],sa[i],w)?p:++p; } } } void get_height(int n){ int i; for(i=1;i<=n;i++){ if(rk[i]==1) continue; int x=max(h[rk[i-1]]-1,0); while(i+x<=n&&a[i+x]==a[sa[rk[i]-1]+x]) x++; h[rk[i]]=x; } } void init(){ int i; a[n+1]=0; for(i=0;i<=n+10;i++){ sum[i]=0; sa[i]=0; rk[i]=0; nxt[i]=0; } } void get_nxt(){ while(q.size()) q.pop(); int i; for(i=1;i<=n;i++){ nxt[i]=n+1; } for(i=1;i<=n;i++){ while(q.size()&&a[q.top()]<a[i]){ nxt[q.top()]=i; q.pop(); } q.push(i); } for(i=1;i<=n;i++){ sum[i]=(ll)num[a[i]-1]*(nxt[i]-i); } for(i=n;i>=1;i--){ sum[i]+=sum[nxt[i]]; } } void pushup(int u){ if(tr[u<<1].mx>=tr[u<<1|1].mx){ tr[u].mx=tr[u<<1].mx; tr[u].id=tr[u<<1].id; } else{ tr[u].mx=tr[u<<1|1].mx; tr[u].id=tr[u<<1|1].id; } } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,a[l],l}; } else{ tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r){ return tr[u].id; } int mid=tr[u].l+tr[u].r>>1; if(r<=mid) return query(u<<1,l,r); else if(l>mid) return query(u<<1|1,l,r); int id1=query(u<<1,l,r); int id2=query(u<<1|1,l,r); if(a[id1]>=a[id2]) return id1; else return id2; } int main(){ ios::sync_with_stdio(false); int i; int t; cin>>t; while(t--){ cin>>n; int i; num.clear(); for(i=1;i<=n;i++){ cin>>a[i]; num.push_back(a[i]); } sort(num.begin(),num.end()); num.erase(unique(num.begin(),num.end()),num.end()); for(i=1;i<=n;i++){ int pos=lower_bound(num.begin(),num.end(),a[i])-num.begin()+1; a[i]=pos; } init(); da(n,200000); get_height(n); get_nxt(); build(1,1,n); ll ans=0; for(i=1;i<=n;i++){ if(h[rk[i]]==0) ans+=sum[i]; else{ int pos=query(1,i,i+h[rk[i]]-1); ans+=sum[nxt[pos]]+1ll*(nxt[pos]-i-h[rk[i]])*num[a[pos]-1]; } } cout<<ans<<endl; } }