找区间连续值(HDU5247)

找连续数

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1033 Accepted Submission(s): 371

Problem Description

小度熊拿到了一个无序的数组，对于这个数组，小度熊想知道是否能找到一个k 的区间，里面的 k 个数字排完序后是连续的。

现在小度熊增加题目难度，他不想知道是否有这样的 k 的区间，而是想知道有几个这样的 k 的区间。

Input

输入包含一组测试数据。

第一行包含两个整数n，m，n代表数组中有多少个数字，m 代表针对于此数组的询问次数，n不会超过10的4次方，m 不会超过1000。第二行包含n个正整数，第 I 个数字代表无序数组的第 I 位上的数字，数字大小不会超过2的31次方。接下来 m 行，每行一个正整数 k，含义详见题目描述，k 的大小不会超过1000。

Output

第一行输"Case #i:"。(由于只有一组样例，只输出”Case #1:”即可)

然后对于每个询问的 k，输出一行包含一个整数，代表数组中满足条件的 k 的大小的区间的数量。

Sample Input

6 2

3 2 1 4 3 5

Sample Output

Case #1:

分析：找某个区间的一些列数是否连续，就看最大值-最小值+1==k且里面的数各不相同，前者可以用RMQ解决，后者需要预处理，枚举每个i向后搜索到j+1遇到前面已经出现过的数字，表示已经重复了，则[i,j]区间内的值一定是不重复的，用vis[i]=j来记录，表示区间[i,vis[i]]内的值都是不重复的，到时对于区间[L,R]首先RMQ求出最值maxi和mini，然后判断区间[i-k+1,i]是否在[i-k+1,vis[i-k+1]]内，num计数。

程序：

  1 #include"stdio.h"
  2 #include"string.h"
  3 #include"stdlib.h"
  4 #include"algorithm"
  5 #include"queue"
  6 #include"math.h"
  7 #include"iostream"
  8 #include"vector"
  9 #define M 10009
 10 #define inf 0x3f3f3f3f
 11 #define eps 1e-9
 12 #define PI acos(-1.0)
 13 #include"map"
 14 #include"vector"
 15 #include"set"
 16 #include"string"
 17 using namespace std;
 18 int vis[10001];
 19 int a[M];
 20 int Log[M],dp_min[M][30],dp_max[M][30];
 21 void init()
 22 {
 23     Log[0] = -1;
 24     for(int i = 1;i <M;i++)
 25         Log[i] = ((i&(i-1)) == 0)?Log[i-1]+1:Log[i-1];
 26 }
 27 void RMQ(int n)
 28 {
 29     int i,j;
 30     int m=Log[n];
 31     for(i=1;i<=n;i++)
 32         dp_min[i][0]=dp_max[i][0]=a[i];//dis代表原数列
 33     for(j=1;j<=m;j++)
 34     {
 35         for(i=1;i<=n+1-(1<<j);i++)
 36         {
 37             dp_max[i][j]=max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);
 38             dp_min[i][j]=min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);
 39         }
 40     }
 41 }
 42 int lcp_min(int x,int y)
 43 {
 44     int m=Log[y-x+1];
 45     return min(dp_min[x][m],dp_min[y+1-(1<<m)][m]);
 46 }
 47 int lcp_max(int x,int y)
 48 {
 49     int m=Log[y-x+1];
 50     return max(dp_max[x][m],dp_max[y+1-(1<<m)][m]);
 51 }
 52 int main()
 53 {
 54 
 55     int kk=1;
 56     int n,m;
 57     while(scanf("%d%d",&n,&m)!=-1)
 58     {
 59 
 60         for(int i=1;i<=n;i++)
 61             scanf("%d",&a[i]);
 62         init();
 63         RMQ(n);
 64         map<int,int>mp;
 65         memset(vis,0,sizeof(vis));
 66         for(int i=1;i<=n;i++)
 67         {
 68             mp[a[i]]=i;
 69             vis[i]=i;
 70             int j;
 71             for(j=i+1;j<=n;j++)
 72             {
 73                 if(mp[a[j]]==0)
 74                 {
 75                     mp[a[j]]=j;
 76                     vis[i]=j;
 77                 }
 78                 else
 79                 {
 80                     break;
 81                 }
 82             }
 83             if(j==n+1)//小优化，如果区间[i,n]都不相同则[k,n]的所有区间也都不同(k>=i)
 84             {
 85                 for(int j=i+1;j<=n;j++)
 86                     vis[j]=n;
 87                 break;
 88             }
 89             for(int k=i;k<=j;k++)
 90                 mp[a[k]]=0;
 91         }
 92         printf("Case #%d:
",kk++);
 93         while(m--)
 94         {
 95             int k;
 96             scanf("%d",&k);
 97             int num=0;
 98             if(k>n)
 99             {
100                 printf("0
");
101                 continue;
102             }
103             for(int i=k;i<=n;i++)
104             {
105                 int maxi=lcp_max(i-k+1,i);
106                 int mini=lcp_min(i-k+1,i);
107                 if(maxi-mini==k-1&&vis[i-k+1]>=i)
108                     num++;
109             }
110             printf("%d
",num);
111         }
112     }
113     return 0;
114 }

View Code