题意：
给定一个序列ai，个数为n。再给出一系列w；
对于每个w，求序列中，所有长度为w的连续子串中的权值和，子串权值为子串中不同数的个数
解析：
一直想不出来怎么转移，看了网络上面的题解才明白怎么做。
dp[i]表示w=i时所求的答案。
dp[1]=n，这个很容易知道，
dp[2]中的子串就是删去dp[1]中最后一个子串，
再令每个子串加上 其之后的那个数，以此类推
要删去的最后一个子串的权值很好求，for一遍就能预处理出来。（利用数组映射）
last[i] 表示 w=i 的最后一个子串权值。
难的就是求加上一个数后所加的权值：
令C[i]表示：i这个数与它前面相同值的最近距离，这也能for一遍预处理出来。（利用数组映射）
之后求出sum[i]，表示两同值数最短距离大于等于i的值。（可以利用树状数组优化）
对于dp[i−1]推dp[i]，每个子串加上后面一个数，只有当这个数与它前面同值数最短距离大于等于i时才会加权值，否则会重复而不加。所以可以推出递推式：
dp[i]=dp[i−1]−num[i−1]+sum[i]
dp[1]=n
注意：
处理c[i]的时候，如果一个数ai前面没有相同的数，则距离计算为到0的距离i。
因为加上这类数也是成立。
答案dp[i]会超int。
my code
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = (int)1e6 + 10;int n, m;ll dp[N], C[N];int pos[N], last[N], a[N];bool vis[N];inline int lowbit(int x) { return x & (-x); }ll getSum(int x) {ll ret = 0;while(x > 0) {ret += C[x];x -= lowbit(x);}return ret;}void add(int x) {while(x <= n) {C[x]++;x += lowbit(x);}}void init() {memset(vis, false, sizeof(vis));memset(pos, 0, sizeof(pos));memset(C, 0, sizeof(C));}inline ll query(int ql, int qr) {return getSum(qr) - getSum(ql-1);}void solve() {// getLastlast[0] = 0;for(int i = n, j = 1; i >= 1; i--, j++) {last[j] = last[j-1] + !vis[a[i]];vis[a[i]] = true;}//getCfor(int i = 1; i <= n; i++) {add(i - pos[a[i]]);pos[a[i]] = i;}dp[1] = n;for(int i = 2; i <= n; i++) {dp[i] = dp[i-1] - last[i-1] + query(i, n);}}int main() {int w;while(~scanf("%d", &n) && n) {for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]);}init();solve();scanf("%d", &m);while(m--) {scanf("%d", &w);printf("%lld\n", dp[w]);}}return 0;}
