看到还没有题解，那就来一发 相对于说这题是dp，我觉得更像是体现了数组预处理信息的一种递推，很巧妙的运用数组储存信息

• 由数据范围知肯定要提前预处理，时间复杂度为O(n),那么容易想到每个区间存在关联，比如f[4]比f[3]多了一个数，贡献在于f[3]中是否有此多出的数，转化一下问题 f【4】新增的数到之前最近出现位置的距离是否>=4，若大于则有贡献1，可推广到整个区间上的所有子区间
• 下面转移方程f[i]=f[i-1]+cnt[i]-diff[i-1],cnt[i]代表距离>=i的满足个数，因为整个区间包含多个所要更新的子区间，而总贡献即为cnt【i】，之前我们要先处理last[i]数组，为距离数组，diff[i]是一个后缀数组，为增大区间后少掉的那个区间

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+8;
int n,q,a[N],last[N],diff[N],dp[N],x,cnt[N],cnt1[N];
int mp[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        last[i]=i-mp[a[i]];
        mp[a[i]]=i;
    }
    for(int i=1;i<=n;i++)cnt[last[i]]++;
    for(int i=n;i>=1;i--){
        cnt[i-1]+=cnt[i];
    }
    memset(mp,0,sizeof(mp));
    int sum=0;
    for(int i=n;i>=1;i--){
        if(!mp[a[i]]){
            sum++;
            mp[a[i]]++;
        }
        diff[n-i+1]=sum;
    }
    dp[1]=n;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+cnt[i]-diff[i-1];
    }
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        printf("%d\n",dp[x]);
    }
    return 0;
}