Substrings

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1727    Accepted Submission(s): 518

7

1 1 2 3 4 4 5

3

1

2

3

0

7

10

12

1、
非常明显，长度为1的答案为dp[1]=n;

2、
长度为2的为dp[2]=dp[1]+x-y=7+4-1=10；

X为添加的一个数和前边不同的个数，{1,1}，{1,2}，{2,3}，{3,4}，{4,4}，{4,5} 为4；

Y为去掉的不足2的区间有几个不同数字，长度为1的最后一个区间{5},须要舍去。为1；

3、

长度为3的为dp[3]=dp[2]+x-y=10+4-2=12。

X为添加的一个数和前边不同的个数，{1,1,2}。{1,2,3}，{2,3,4}。{3,4,4}，{4,4,5}为4；

Y为去掉的不足3的区间有几个不同数字。长度为2的最后一个区间{4,5},须要舍去，为2；

所以，我们须要得到当前数字和它上次出现的位置差的大小。详细实现看代码。。

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<iostream>

using namespace std;

#define N 1000005

#define LL __int64

const int inf=0x1f1f1f1f;

int a[N],len[N],pre[N],vis[N],f[N];

LL dp[N];

int main()

{

    int i,n,m;

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

    {

        memset(pre,-1,sizeof(pre)); //记录一个值上次出现的位置

        memset(len,0,sizeof(len)); //len[i]：有几个间隔为i的数

        memset(dp,0,sizeof(dp));   //记录终于答案

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

        {

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

            len[i-pre[a[i]]]++;

            pre[a[i]]=i;

        }

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

            len[i]+=len[i+1];

        memset(f,0,sizeof(f));   //f[i]从后往前记录后i个数有几个不同值

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

        for(i=1;i<n;i++)

        {

            f[i]=f[i-1];

            if(!vis[a[n-i]])

            {

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

                f[i]++;

            }

        }

        dp[1]=n;

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

            dp[i]=dp[i-1]+len[i]-f[i-1];

        scanf("%d",&m);

        while(m--)

        {

            scanf("%d",&i);

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

        }

    }

    return 0;

}