HDU 4455.Substrings

Substrings

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3240    Accepted Submission(s): 990

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

7
1 1 2 3 4 4 5
3
1
2
3
0

Sample Output

7
10
12

Source

2012 Asia Hangzhou Regional Contest

Recommend

We have carefully selected several similar problems for you:  6018 6017 6016 6015 6014 

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4455

题意：有n个数，q个询问。求每次询问的连续长度为w的子数组权值的和。数组的权值为数组内不相同的数的个数。

转载来自：http://blog.csdn.net/gotoac/article/details/8188437

思路：

拿样例写一下

1: {1},           {1},           {2},        {3},            {4},          {4},          {5}

2: {1,1},        {1,2},        {2,3},      {3,4},         {4,4},       {4,5}

3: {1,1,2},     {1,2,3},     {2,3,4},    {3,4,4},      {4,4,5}

4: {1,1,2,3},  {1,2,3,4},  {2,3,4,4},  {3,4,4,5}

...

容易发现可以得出一个发现:

长度为w的值肯定包含长度为w-1的值减去最后一个字数组的权值和

例:

2: {1,1} ,　 {1,2} ,    {2,3} ,    {3,4} ,    {4,4} ,   {4,5}

3: {1,1,} , {1,2,} , {2,3,} , {3,4,} , {4,4,} 

dp[3] = dp[2] - 权值[{4,5}] + ?

而'?'就表示添加上那些标蓝色的数之后要添加的值.

设某个标蓝色的数为a[i],另外一个和它相等的且和它最近的数为a[j],且i>j

如果i-j>w的话那么添上这个标蓝的数就可以使得dp[w]+1

所以我们只要求出cnt[dis]即可,dis既某数离在它之前且相等的且和它最近的数的距离.

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MAXN=1e6+,inf=0x3f3f3f3f,mod=1e9+;
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
int a[MAXN];
int cnt[MAXN],dp[MAXN];
ll sign[MAXN];
void run(int n)
{
    memset(cnt,,sizeof(cnt));
    memset(sign,,sizeof(sign));
    for(int i=; i<=n; i++)
    {
        scanf("%d",&a[i]);
        int x=i-sign[a[i]];
        cnt[i-sign[a[i]]]++;
        sign[a[i]]=i;   ///sign[i]表示i的位置
        //cout<<x<<" "<<cnt[x]<<endl;
    }
    memset(dp,,sizeof(dp));
    memset(sign,,sizeof(sign));
    for(int i=n,t=; i>; i--,t++)
    {
        if(sign[a[i]]) dp[t]=dp[t-];
        else dp[t]=dp[t-]+,sign[a[i]]=;  ///sign[i]标记i是否出现过
    }
    memset(sign,,sizeof(sign));
    int t=n;
    for(int i=; i<=n; i++)
    {
        sign[i]=sign[i-]-ll(dp[i-]);
        t-=cnt[i-];
        sign[i]+=t;
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n!=)
    {
        run(n);
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int w;
            scanf("%d",&w);
            cout<<sign[w]<<endl;
        }
    }
    return ;
}