AT_arc170_b 的题解

（一）

因为 \(a_i\) 较小，那么可以对每一个 \(i\)，求出它右边离他最近的值为 \(j\) 的位置。

枚举左端点和中间那个数 \(a_j\)，那么可以求出最小的 \(k\)。

这样就求出了每个左端点可以取到的最小的 \(k\)，记为 \(b_i\) 再从右到左 \(b_i=\min(b_i,b_{i+1})\)。

（二）

AC 代码。

#include<bits/stdc++.h>
#define db double
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
int n,a[100010],las[100010],pos[100010][11];
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=read();
    for(int i=1;i<=n;i++)
    	a[i]=read(),las[i]=n+1;
    las[n+1]=n+1;
    for(int i=1;i<=10;i++)
    	pos[n][i]=pos[n+1][i]=n+1;
    for(int i=n-1;i>=1;i--){
    	for(int j=1;j<=10;j++)
    		pos[i][j]=pos[i+1][j];
    	pos[i][a[i+1]]=i+1;
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=10;j++){
    		if(j*2-a[i]<1||j*2-a[i]>10||pos[i][j]>n)continue;
    		int z=pos[pos[i][j]][j*2-a[i]];
    		if(z>n)continue;
    		las[i]=min(las[i],z);
    	}
    }
    for(int i=n;i>=1;i--)
    	las[i]=min(las[i],las[i+1]);
    int res=0;
    for(int i=1;i<=n;i++)
    	res+=n-las[i]+1;
    printf("%lld\n",res);
    return 0;
}