找连续数
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
3
4
Sample Output
Case #1:
2
2
分析：找某个区间的一些列数是否连续，就看最大值-最小值+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计数。
程序：
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"queue"
#include"math.h"
#include"iostream"
#include"vector"
#define M 10009
#define inf 0x3f3f3f3f
#define eps 1e-9
#define PI acos(-1.0)
#include"map"
#include"vector"
#include"set"
#include"string"
using namespace std;
int vis[];
int a[M];
int Log[M],dp_min[M][],dp_max[M][];
void init()
{
Log[] = -;
for(int i = ;i <M;i++)
Log[i] = ((i&(i-)) == )?Log[i-]+:Log[i-];
}
void RMQ(int n)
{
int i,j;
int m=Log[n];
for(i=;i<=n;i++)
dp_min[i][]=dp_max[i][]=a[i];//dis代表原数列
for(j=;j<=m;j++)
{
for(i=;i<=n+-(<<j);i++)
{
dp_max[i][j]=max(dp_max[i][j-],dp_max[i+(<<(j-))][j-]);
dp_min[i][j]=min(dp_min[i][j-],dp_min[i+(<<(j-))][j-]);
}
}
}
int lcp_min(int x,int y)
{
int m=Log[y-x+];
return min(dp_min[x][m],dp_min[y+-(<<m)][m]);
}
int lcp_max(int x,int y)
{
int m=Log[y-x+];
return max(dp_max[x][m],dp_max[y+-(<<m)][m]);
}
int main()
{ int kk=;
int n,m;
while(scanf("%d%d",&n,&m)!=-)
{ for(int i=;i<=n;i++)
scanf("%d",&a[i]);
init();
RMQ(n);
map<int,int>mp;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
mp[a[i]]=i;
vis[i]=i;
int j;
for(j=i+;j<=n;j++)
{
if(mp[a[j]]==)
{
mp[a[j]]=j;
vis[i]=j;
}
else
{
break;
}
}
if(j==n+)//小优化，如果区间[i,n]都不相同则[k,n]的所有区间也都不同(k>=i)
{
for(int j=i+;j<=n;j++)
vis[j]=n;
break;
}
for(int k=i;k<=j;k++)
mp[a[k]]=;
}
printf("Case #%d:\n",kk++);
while(m--)
{
int k;
scanf("%d",&k);
int num=;
if(k>n)
{
printf("0\n");
continue;
}
for(int i=k;i<=n;i++)
{
int maxi=lcp_max(i-k+,i);
int mini=lcp_min(i-k+,i);
if(maxi-mini==k-&&vis[i-k+]>=i)
num++;
}
printf("%d\n",num);
}
}
return ;
}