dp解法 1s
注意long long ，dp[I+1] = dp[I] 减去因为长度增加而少掉的最后一组的权值，再加上不重复的数字，即与前一个相同值大于长度I的值。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1000100 ;
typedef long long ll ;
int c[MAX] , pre[MAX] , num[MAX] , sum[MAX] ,read[MAX]; ll dp[MAX] ;/// attention the long long
int main(){int n ;while( ~ scanf("%d" , &n) && n ){for(int i = 1 ; i <= n ; i ++ ) scanf("%d" , &read[i]) ;memset(c , 0 , sizeof(c)) ;memset(pre , 0 , sizeof(pre)) ;for(int i = 1 ; i <= n ; i ++ ){c[ i -pre[ read[i] ] ] ++ ;pre[ read[i] ] = i ;}sum[n] = c[n] ;for(int i = n-1 ; i >= 1 ; i -- )sum[i] = sum[i+1] + c[i] ;memset(c , 0 , sizeof(c)) ;num[1] = 1 ;c[ read[n] ] ++ ;for(int i = 2 ; i <= n ; i ++ ){if(c[ read[n - i + 1 ] ] == 0 ){num[i] = num[i-1] + 1 ;c[ read[n-i+1] ] = 1 ;}elsenum[i] = num[i-1] ;}///every time length + 1 , and the number of group - 1 , so we should minus the last one 's weight and others add the sumdp[1] = n ;for(int i = 2 ; i <= n ; i ++ )dp[i] = dp[i-1] + sum[i] - num[i-1] ;int op , temp ;scanf("%d" , &op) ;while( op -- ){scanf("%d" , & temp ) ;printf("%lld\n" , dp[temp]) ;}}return 0 ;
}