题意
通过不断在某个位置添加 \((1,2,\dots ,k)\) 所形成的序列称为可生成的。求给定序列有多少区间是可生成的。
分析
我们把一个可生成的序列看成很多依次加一的区间 \((x,x+1,\dots,y)\) 构成的，很明显发现，对于每一个区间，总是满足前面有一段的结尾是 \(x-1\) 或 \(x=1\)。
这样的限制条件只在乎前面的，而不用考虑后面的，所以可以得到结论：
如果一个序列是可生成的，那么它的每一个前缀都是可生成的。
有了这个性质，可以考虑枚举左端点，然后找到最右边的点，使这个区间是可生成的。虽然看上去可以二分，但是很快发现，无法在 \(O(1)\) 时间判断一个区间是不是可生成的。这个思路就无法再继续了。
继续观察序列，又发现一个性质：
如果一个可生成的序列包含了另一个可生成的序列，那么被包含的序列一定是连续的。
举个例子，\((1,2,1,2,3,3,1,2,4)\) 就是这样的关系，里面的 \((1,2,3)\) 和 \((1,2)\) 是连续的。
看上去这个性质十分的废话，实际上，这等同于告诉我们：如果剔除了一个可生成的序列内部的其他可生成序列，最后会剩下以 \(1\) 开始，依次加一的序列。
实现上，可以使用链表，倒序遍历，算出每个 \(1\) 最远到达的地方。如果遍历到 \(1\)，就利用之前得出的答案往后枚举，并记录当前的答案，每个元素只会枚举两次，复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5e5+10;
int n,a[N],l[N],r[N];
ll ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
r[i]=i+1,l[i]=i-1;
}
for(int i=n;i>=1;--i){
if(a[i]==1){
int ff=1;
for(int j=i,k=1;j<=n;j=r[j],++k){
if(a[j]!=k){
r[i]=j;
l[j]=i;
ans+=j-i;
ff=0;
break;
}
}
if(ff){
ans+=n-i+1;
r[i]=n+1;
l[n+1]=i;
}
r[l[i]]=r[i];
l[r[i]]=l[i];
}
}
printf("%lld",ans);
return 0;
}