学步园

参考http://www.cnblogs.com/kuangbin/archive/2012/11/11/2765329.html

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000100
typedef long long ll;
using namespace std;            //这里理解a[0]与所以数都相等，利于后面递推
int n,m,a[N],pre[N],fin[N],s[N],last[N];//s[j]表示 a[i]-pre[a[i]]==j,1<=i<=n的t的个数,即离上一个相等元素的距离为i的个数
ll dp[N];                       //fin[i]表示最后的i个数含有的不同元素的个数
void solve(){
    int i,j;
    memset(pre,0,sizeof(pre));
    memset(s,0,sizeof(s));
    memset(last,0,sizeof(last));
    for(i=1;i<=n;i++){
        if(pre[a[i]]){
            last[i]=pre[a[i]];
            s[i-pre[a[i]]]++;
        }
        pre[a[i]]=i;
    }
    memset(fin,0,sizeof(fin));
    fin[1]=1;
    for(i=2;i<=n;i++){
        if(pre[a[n-i+1]]==n-i+1)
            fin[i]=fin[i-1]+1;
        else
            fin[i]=fin[i-1];
    }
    memset(dp,0,sizeof(dp));
    dp[1]=n;
    int sum=n;
    for(i=2;i<=n;i++){
        dp[i]=dp[i-1]-fin[i-1];
        sum-=s[i-1];
        if(last[i-1]==0)sum--;
        dp[i]+=sum;
    }
}
int main(){
    int i,j,tem;
    while(scanf("%d",&n)){
        if(n==0)break;
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        solve();
        for(i=1;i<=m;i++){
            scanf("%d",&tem);
            printf("%I64d\n",dp[tem]);
        }
    }
    return 0;
}