Substrings
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3240 Accepted Submission(s): 990
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
Each test case starts with a positive integer n, the array length. The next line consists of n integers a1,a2…an, 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<=106, 0<=Q<=104, 0<= a1,a2…an <=106
1 1 2 3 4 4 5
3
1
2
3
0
10
12
拿样例写一下
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 ;
}