Problem Description

XXX has an array of length n. XXX wants to know that, for a given w, what is the sum of the distinct elements’ number in all substrings of length w. For example, the array is { 1 1 2 3 4 4 5 } When w = 3, there are five substrings of length 3. They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
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

 

Input

There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a₁,a₂…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⁶, 0<=Q<=10⁴, 0<= a₁,a₂…a_n <=10⁶

 

Output

For 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

 

Sample Output

 

Source

 

Recommend

#include<cstdio>

#include<cstring>

using namespace std;

const int N=1e6+;

int n,num[N];

int cx[N],add[N],lnc[N];

long long f[N];

void Discretization(){

    memset(cx,,sizeof cx);

    memset(lnc,,sizeof lnc);

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

        if(!cx[num[n-i+]]){

            cx[num[n-i+]]=;

            lnc[i]=lnc[i-]+;

        }

        else{

            lnc[i]=lnc[i-];

        }

    }

    memset(cx,,sizeof cx);

    memset(add,,sizeof add);

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

        add[i-cx[num[i]]]++;

        cx[num[i]]=i;

    }

}

void DynamicProgramming(){

    memset(f,,sizeof f);

    f[]=n;int delta=n;

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

        f[i]=f[i-]-lnc[i-];

        delta-=add[i-];

        f[i]+=delta;

    }

}

void Solution(){

    int Q,x;

    for(scanf("%d",&Q);Q--;) scanf("%d",&x),printf("%lld\n",f[x]);

}

int main(){

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

        for(int i=;i<=n;i++) scanf("%d",&num[i]);

        Discretization();

        DynamicProgramming();

        Solution();

    }

    return ;

}