The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12
InputThere are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a 1,a2…a n, representing the elements of the array.
Then there is a line with an integer Q, the number of queries. At last Q lines follow, each contains one integer w, the substring length of query. The input data ends with n = 0 For all cases, 0<w<=n<=10 6, 0<=Q<=10 4, 0<= a 1,a 2…a n <=10 6OutputFor each test case, your program should output exactly Q lines, the sum of the distinct number in all substrings of length w for each query.Sample Input
7
1 1 2 3 4 4 5
3
1
2
3
0
Sample Output
7
10
12
这真是道好题啊，dp的题 看题解理解起来真费劲。
题意：给一个序列，将其分为长度为m的集合，求每个集合的 不同元素的个数 之和。
解题思路：一开始我是想到线段树和树状数组，但是因为对这些掌握的不太熟，只会加减乘gcd，而且找不到子集和母集合直接关系，感觉是dp，但是无从下手。后来看了好久的题解，最后才明白。
题解地址：http://blog.csdn.net/a601025382s/article/details/12283581
题解内容：
题意：
给定一个序列ai，个数为n。再给出一系列w；对于每个w，求序列中，所有长度为w的连续子串中的权值和，子串权值为子串中不同数的个数
题解：
一道动态规划体。。一开始i想成了树状数组。dp[i表示w=i时所求的答案。dp[1]=n，这个很容易知道，dp[2]中的子串就是删去dp[1]中最后一个子串，再每个子串加上其之后的那个数，以此类推。。
要删去的最后一个子串的权值很好求，for以遍就能预处理，num[i]表示w=i的最后一个子串权值。难的就是求加上一个数后所加的权值：另c[i]表示一个数与它前面值相同的最近距离，这也能for一遍预处理。之后求出sum[i]，表示两同值数最短距离大于等于i的值。对于dp[i-1]推dp[i],加上一个数，只有当这个数与它前面同值数最短距离大于等于i时才会加权值，否则会重复而不加。所以可以推出递推式：dp[i]=dp[i-1]-num[i-1]+sum[i],dp[1]=n;
注意：
1.处理c[i]的时候，如果一个数ai前面没有相同的数，则距离计算为到0的距离i，why？因为加上这类数也是成立。
2.答案dp[i]会超int，我就wa了好几次。。
这题的思路就是，比如集合长度len为1的时候，每个集合不同元素的个数c肯定是1，而len加1时，因为总共就n个数，集合的总数量肯定会减1，也就是最后一个集合会消失。而c是否会加，取决于新加的这个元素在集合中有没有相同的数。所以我们要预处理每个数与其前面最近的相同的数的距离,如果与最近的相同数的距离大于集合的长度，也就是说在集合外，那么把这个数加入集合c就会加1。我们把距离为i的相同数的个数存在cnt[i]数组里面。这样我们求长度为2的时候，只需要先把除了长度小于2的cnt全加上，再减去长度为1时最后一个集合的值就是答案。
所以最后的公式就是dp[i]=dp[i-1]-last[i-1]+sum[i];//sum[i]为cnt从i到n的和。
注意，这里计算记录cnt数组的时候，不需要记录距离为i的两个相同数的位置，因为这些子集把n个数完全覆盖，所以无论这两个数在哪，都会被考虑在子集中，不明白的话可以自己用一个例子模拟一下，会发现只需要记距离为i的个数有多少就行了。
1 #include <stdio.h>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <cmath>
6 #include <stack>
7 #include <queue>
8 typedef long long ll;
9 const int maxn = 1e6+5;
10 int nu[maxn],pre[maxn],cnt[maxn],sum[maxn],lt[maxn];
11 ll dp[maxn]; //dp会爆int
12 using namespace std;
13
14 int main(){
15 ios::sync_with_stdio(false);
16 int n,m,t;
17 while(cin>>n,n)
18 {
19 memset(dp,0,sizeof(dp));
20 memset(pre,0,sizeof(pre));
21 memset(cnt,0,sizeof(cnt));
22 memset(sum,0,sizeof(sum));
23 memset(lt,0,sizeof(lt));
24
25 for(int i=1;i<=n;++i) cin>>nu[i];
26
27 for(int i=1;i<=n;++i) //求出相同的值距离为i的数有多少对
28 {
29 cnt[i-pre[nu[i]]]++;
30 pre[nu[i]]=i;
31 }
32 sum[n]=cnt[n];
33 for(int i=n-1;i>=1;i--) //把cnt的和按len=n到1的顺序存在sum数组里面。便于最后操作
34 {
35 sum[i]=sum[i+1]+cnt[i];
36 }
37 memset(pre,0,sizeof(pre));
38 lt[1]=1;
39 pre[nu[n]]++;
40 for(int i=2;i<=n;++i) //记录最后一个集合的不同元素个数
41 {
42 if(pre[nu[n-i+1]])
43 lt[i]=lt[i-1];
44 else
45 {
46 lt[i]=lt[i-1]+1;
47 pre[nu[n-i+1]]=1;
48 }
49 }
50 dp[1]=n;
51 for(int i=2;i<=n;++i)
52 {
53 dp[i]=dp[i-1]+sum[i]-lt[i-1];//重点
54 }
55 cin>>m;
56 for(int i=0;i<m;++i)
57 {
58 cin>>t;
59 cout<<dp[t]<<endl;
60 }
61 }
62 return 0;
63 }