题意： 给一串数字，给q个查询，每次查询长度为w的所有子串中不同的数字个数之和为多少。
解法：先预处理出D[i]为： 每个值的左边和它相等的值的位置和它的位置的距离，如果左边没有与他相同的，设为n+8（看做无穷）。
考虑已知w=k的答案，推w = k+1时，这时每个区间都将增加一个数，即后n-k个数会增加到这些区间中，容易知道，如果区间内有该数，那么个数不会加1，,即D[i] > k时，结果++，即查询后n-k个数有多少个D[i] > k 的数即为要加上的数，然后最后面还会损失一个区间，损失的是不能增加一个数的那个区间，随着w的增加，该区间会向左边伸展，所以记录一下该区间有多少个不同的数即可。 求区间内有多少个D[i]>k可以用树状数组先求有多少个D[i]<=k（getsum(k)），然后区间长度减一下即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std;
#define N 1000107 int c[N],n,D[N],Last,vis[N],a[N],pos[N],L[N];
lll sum[N]; int lowbit(int x) { return x&-x; }
void modify(int x,int val)
{
while(x <= n+)
{
c[x]+=val;
x += lowbit(x);
}
} int getsum(int x)
{
int res = ;
while(x > )
{
res += c[x];
x -= lowbit(x);
}
return res;
} int main()
{
int q,i,j,w;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<=n;i++)
scanf("%d",&a[i]);
memset(pos,,sizeof(pos));
for(i=;i<=n;i++)
{
int x = a[i];
D[i] = i-pos[x];
if(D[i] == i) D[i] = n+;
pos[x] = i;
}
memset(c,,sizeof(c));
memset(vis,,sizeof(vis));
for(i=;i<=n;i++)
modify(D[i],);
sum[] = n;
Last = ;
vis[a[n]] = ;
for(i=;i<=n;i++)
{
sum[i] = sum[i-]+(n-i+-getsum(i-))-Last;
modify(D[i],-);
if(!vis[a[n-i+]])
{
vis[a[n-i+]] = ;
Last++;
}
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&w);
printf("%I64d\n",sum[w]);
}
}
return ;
}