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
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 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
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
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
Recommend
题意:有n个数,q个询问。求每次询问的连续长度为w的子数组权值的和。数组的权值为数组内不相同的数的个数。
思路:
拿样例写一下
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,2} , {1,2,3} , {2,3,4} , {3,4,4} , {4,4,5}
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+100,inf=0x3f3f3f3f,mod=1e9+7; #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,0,sizeof(cnt)); memset(sign,0,sizeof(sign)); for(int i=1; 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,0,sizeof(dp)); memset(sign,0,sizeof(sign)); for(int i=n,t=1; i>0; i--,t++) { if(sign[a[i]]) dp[t]=dp[t-1]; else dp[t]=dp[t-1]+1,sign[a[i]]=1; ///sign[i]标记i是否出现过 } memset(sign,0,sizeof(sign)); int t=n; for(int i=1; i<=n; i++) { sign[i]=sign[i-1]-ll(dp[i-1]); t-=cnt[i-1]; sign[i]+=t; } } int main() { int n; while(scanf("%d",&n)&&n!=0) { run(n); int q; scanf("%d",&q); while(q--) { int w; scanf("%d",&w); cout<<sign[w]<<endl; } } return 0; }