记$cnt_{v}$表示答案$\ge v$的区间数量，则问题即求$\sum_{v\ge 1}cnt_{v}$
记$f_{l}$表示最大的右端点$r$满足区间$[l,r)$的答案$
初始$v=1$且$f_{l}=l$，当$v\rightarrow v+1$时转移即$f'_{l}=\begin{cases}l+1&a_{l}=v\\f_{f_{l}}&a_{l}\ne v\end{cases}$，时间复杂度为$o(n^{2})$
结论1：对于所有$v$，答案为$v$的极长区间数之和为$o(n\log n)$
记$f_{n}$为$n$时的答案，归纳证明$f_{n}\le o(\log n!)\le o(n\log n)$
设$a_{p}$为最大值，则$f_{n}=f_{p-1}+f_{n-p}+$包含$p$的极长区间数
在确定左端点后$l$后，显然$[l,n]$的答案$\le [l,p]$的答案$+o(\log \frac{n}{p})$，因此至多$o(\log \frac{n}{p})$个极长区间?
对于所有$o(p)$个左端点，包含$p$的极长区间数$\le o(p\log \frac{n}{p})\le o(\sum_{i=0}^{p-1}\log \frac{n-i}{p-i})=o(\log\frac{n!}{p!(n-p)!})$
代入原式显然成立，即得证
结合上述结论，考虑以下优化——
优化1：仅维护所有极长且非空的区间$[l,f_{l})$，由于$f$单调不降，条件即$\max(l,f_{l-1})
在此基础上，转移分为两步：
1.将区间$[l,f_{l})$替换为$[l,f'_{l})$，其中$f_{f_{l}}$可以双指针求出（注意判断$[l,f'_{l})$是否极长）
2.对于$a_{l}=v$的位置，新增区间$[l,l+1)$，可以用归并排序与前者合并
优化2：若$\min(a_{l-1},a_{f_{l}})\ge v$，则$f'_{l}=f_{l}$（转移不影响），将其单独存储在$l$和$f_{l}$上
显然每一个位置至多存储一个，并在$a_{l}=v$时将$l$和$l+1$上存储的区间重新维护即可
结论2：上述做法的时间复杂度为$o(n\log n)$
不难发现，所有维护/存储（包括优化2）的区间$[l,f_{l})$即答案$
关于转移的第1步，对$[l,f'_{l})$是否极长分类讨论：
1.若不极长，即使得区间个数-1，可以均摊到加入区间时
2.若极长，结合$\min(a_{l-1},a_{f_{l}})
两者均包含$[l,f_{l})$，因此$[l,f'_{l})$极长的必要条件为$f_{l}
进一步的，$[l,f'_{l})$必然是答案为$v$的极长区间，根据结论1总复杂度至多为$o(n\log n)$
另外，转移的第2步和优化2存储的复杂度显然均为$o(n)$，即得证
1 #include
2 using namespace std;
3 #define N 300000
4 #define M 1000100
5 #define ll long long
6 #define pii pair
7 #define mp make_pair
8 #define fi first
9 #define se second
10 int n,a[N];ll sum,ans;pii f0[N];
11 vector<int>v[M];vectorg,f;
12 void add(pii k){
13 f0[k.fi]=f0[k.se]=k;
14 sum+=(ll)(k.se-k.fi)*(k.se-k.fi+1)/2;
15 }
16 void dec(pii k){
17 f0[k.fi]=f0[k.se]=mp(0,0);
18 sum-=(ll)(k.se-k.fi)*(k.se-k.fi+1)/2;
19 }
20 int main(){
21 scanf("%d",&n);
22 for(int i=1;i<=n;i++){
23 scanf("%d",&a[i]);
24 v[a[i]].push_back(i);
25 }
26 for(int i=1;i){
27 g.clear(),ans+=(ll)n*(n+1)/2-sum;
28 for(int x=0;x){
29 int s=min(f[x].se,(x+11].fi-1 : n));
30 ans-=(ll)((f[x].se-s)+(f[x].se-f[x].fi))*(s-f[x].fi+1)/2;
31 }
32 for(int x=0,y=0;x){
33 while ((y+11].fi<=f[x].se))y++;
34 if ((g.empty())||(g.back().se<f[y].se))g.push_back(mp(f[x].fi,f[y].se));
35 }
36 f.clear();
37 for(int x=0,y=0;x<=g.size();x++){
38 int s=(x1);
39 while ((ys)){
40 int k=v[i][y];
41 if (f0[k].fi)f.push_back(f0[k]),dec(f0[k]);
42 f.push_back(mp(k,k+1));
43 if (f0[k+1].fi)f.push_back(f0[k+1]),dec(f0[k+1]);
44 y++;
45 }
46 if (x<g.size()){
47 bool flag=0;
48 if ((g[x].fi>1)&&(a[g[x].fi-1]<=i))flag=1;
49 if ((g[x].se<=n)&&(a[g[x].se]<=i))flag=1;
50 if (!flag)add(g[x]);
51 else f.push_back(g[x]);
52 }
53 }
54 }
55 printf("%lld\n",ans);
56 return 0;
57 }