nyoj 975 Distinct Count

Distinct Count

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述: 给一个长度为 n 的数列 {an} ，找出有多少个长度为 m 的区间，使区间中不含有重复的数字。

输入

多组测试数据。（200组）
第 1 行有 2 个数，n,m。（1<=n,m<=10^5）
接下来 1 行有 n 个数，ai。(|ai|<=10^9)

输出

1 行有 1 个数，满足条件的区间的个数。

样例输入

6 3
1 6 2 6 3 6

样例输出

2
讲解：昨天下午和晚上，我和zz都在想这道题，昨天夜里睡觉之前想了下，还是没思路，今天早晨读书时突发灵感啊，算是想清楚了，嘎嘎，特来纪念一下；
我们可以采用左减，右加的方式来解决；依次向右滑动；
线把前m个出现的数标记成1，当然会有重复的，于是用 map 进行计重；map的指向为与之相同前一个数的下标；
也就是说把n个中出现多次的数，只把，最后一个数，标记为1，前面的都为0；然后求和时，这个数，就算了一次；
案例：sum 每 n个数的和；
7 3
1 6 2 6 3 6 7
1 1 1           sum=3;
1 0 1 1         sum=sum-b[1]  =2
1 0 1 1 1       sum=sum+1-b[2]=3
1 0 1 0 1 1     sum=sum-b[3]  =2  //当前的已经出现过了，不在加了，只减去前面的
1 0 1 0 1 1 1   sum=sum+1-b[4]=3

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<cmath>
 7 #include<map>
 8 #include<queue>
 9 using namespace std;
10 const int N=1e5+5;
11 int a[N],b[N];
12 int main()
13 {
14     int ans,sum,m,n;
15     map<long long ,int >ma;
16     while(cin>>m>>n)
17     {
18         ma.clear();
19         memset(b,0,sizeof(b));
20         sum=0;ans=0;
21         for(int i=1 ; i<=m ;i++)
22         {
23             scanf("%d",&a[i]);
24             if(i<=n)
25             {
26             if(ma[ a[i] ]==0)
27             {
28                 sum=sum+1;             //统计前n个共有几个数；
29                 ma[ a[i] ]=i;          //标记一下，下标；
30                  b[i]=1;               //如果此数没有出现，标记为1；
31             }
32             else {
33                       b[ ma[i] ]=0;   //如果已经出现了，把前面的标记为0；
34                       b[i]=1;         //当前的为1；
35                       ma[ a[i] ]=i;   //并更新下标，方便下一次更新；
36                  }
37             }
38         }
39 
40         if(n==1)
41         { printf("%d
",m);continue;}
42         if(sum==n)
43           ans++;
44         for(int i=n+1,j=1; i<=m ; i++,j++)
45         {
46             if(ma[a[i]]==0)//前面没有出现过，直接更新sum，b，ma
47             {
48                 sum=sum+1;
49                 ma[ a[i] ]=i;
50                 b[i]=1;
51             }
52             else {       //出现过了的，前面相同的更新为0，同时更新为新的下标，当前位置标记为1；
53                 b[ma[a[i]]]=0;
54                 ma[a[i]]=i;
55                 b[i]=1;
56             }
57             sum=sum-b[j];    //减去最前面的数，就是这n个数的和；然后判断 sum是否等于n；
58             if(sum==n)
59                 ans++;
60         }
61         cout<<ans<<endl;
62     }
63     return 0;
64 }