题目链接：hdu 4455 Substrings

题目大意：给出n，然后是n个数a[1] ~ a[n]， 然后是q次询问，每次询问给出w， 将数列a[i]分成若干个连续且元素数量为w的集合，计算每个集合中出现的数字种类，输出总和。

解题思路：一开始想到遍历的算法，保持集合元素为w，每次剔除最前一个，加入一个，移动集合，维护数字种类，这种算法的复杂度为o（n^2), 但是超时了，后来看了下题解，dp[i] = dp[i - 1] + sum[i] - cnt;

http://blog.csdn.net/gotoac/article/details/8188437

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

const int N = 1000005;

int n, vis[N], a[N];

__int64 sum[N], cnt,  dp[N];

void init() {

	memset(vis, -1, sizeof(vis));

	memset(sum, 0, sizeof(sum));

	for (int i = 0; i < n; i++) {

		scanf("%d", &a[i]);

		sum[i - vis[a[i]]]++;

		vis[a[i]] = i;

	}

	for (int i = n - 1; i >= 0; i--)

		sum[i] += sum[i + 1];

}

void solve() {

	memset(dp, 0, sizeof(dp));

	dp[1] = n;

	memset(vis, 0, sizeof(vis));

	vis[a[n - 1]] = cnt = 1;

	for (int i = 2; i <= n; i++) {

		dp[i] = dp[i - 1] - cnt + sum[i];

		vis[a[n - i]]++;

		if (vis[a[n - i]] == 1) cnt++;

	}

}

int main () {

	while (scanf("%d", &n), n) {

		init();

		solve();

		int q, w;

		scanf("%d", &q);

		for (int i = 0; i < q; i++) {

			scanf("%d", &w);

			printf("%I64d\n", dp[w]);

		}

	}

	return 0;

}