本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-22 19:32:56

• 题目大意

给定一个长度为$n$的序列，如果区间 $[L,R]$ 中存在 $L \leq i<j<k\leq R$ ,使得 $a_i-a_j=a_j-a_k$ 成立，则这个区间为好区间。问共有多少个好区间。

• 题目分析

为了不重不漏的统计，我们限定右端点 $k$ ,去找符和要求的左端点 $left$ 。 找出符要求的 $i,j,k$ ,可以发现 $a_i,a_j,a_k$ 构成等差数列，数据的范围是 $1...10$ ,符合要求的的情况为 $1，5，9$ ; $10， 6，2$ 等。可以推导出公差的范围为 $-4..4$ .

已知 $a_k$ ,枚举公差，找到符合要求的前两项的值，设数组 $mp[i][j]$ 存储符合要求的最近数值。找到以 $k$ 为结束点的最近 $left$。

如何去维护 $mp[i][j]$ 呢？对于当前点 $k$ 来说，只会改变与 $mp[i][a_k]$ 相关的数据，$mp[i][a_k]=( i$ 出现的最后位置 $)$ 。因此我们还需要用一个桶记录这个位置。

再维护一个 $left$ 的前缀 $max\_left$ ,那么答案就是不断累加从 $1$号结点到 $max\_left$ 的值，也就是 $ans+=max\_left$ 。

时间复杂度为 $O(N \times 10)$ 。

• 参考代码

#include <bits\/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int mp[11][11],l[11];
signed main(){
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int ans=0,lf=0,mlf=0;
	\/\/对每一个右端点q，找其符合要求的最近左端点lf，和前缀最大左端mlf点比较  ans+=mlf
	for(int k=1;k<=n;k++) {
		for(int d=-4;d<=4;d++){\/\/枚举公差 
			if(a[k]+2*d>=1&&a[k]+2*d<=10)lf=max(lf,mp[a[k]+2*d][a[k]+d]);
			mlf=max(mlf,lf);
		}
		ans+=mlf;
		for(int i=1;i<=10;i++){
			if(l[i])mp[i][a[k]]=l[i];
		}
		l[a[k]]=k;	
	}
	
	cout<<ans<<endl;
}