Substrings

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

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

/* ***********************************************Author        :CKbossCreated Time  :2015年08月17日 星期一 22时06分06秒File Name     :HDOJ4455.cpp************************************************ */#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                using namespace std;typedef long long int LL;const int maxn=1001000;int n;LL dp[maxn];int a[maxn];int pre[maxn];int spre[maxn];int wz[maxn];bool vis[maxn];/*************BIT*********************/inline int lowbit(int x) { return x&(-x); }int tree[maxn];void add(int p,int v){ for(int i=p;i
                 
                  =1;i--) { int x=a[i]; if(wz[x]==-1) wz[x]=i; else { spre[wz[x]-i]++; pre[wz[x]]=wz[x]-i; wz[x]=i; } } int zero=0,nozero; for(int i=1;i<=n;i++) { if(pre[i]==0) zero++; if(spre[i]) add(i,spre[i]); } int ed=n; int siz=0; nozero=n-zero; dp[1]=n; zero--; for(int i=2;i<=n;i++) { if(vis[a[ed]]==false) { vis[a[ed]]=true; siz++; } ed--; int B=siz; int A=zero+nozero-sum(i-1); dp[i]=dp[i-1]+A-B; if(pre[i]) nozero--,add(pre[i],-1); else zero--; } int Q; scanf("%d",&Q); while(Q--) { int x; scanf("%d",&x); printf("%lld\n",dp[x]); } } return 0;}

转载地址：http://lyavx.baihongyu.com/

你可能感兴趣的文章