2014
11-27

Coach Yehr’s punishment

During the Mult-University Trainging,Coach Yehr asks all the ACM teammates to jog at 6:30AM.But 6:30 is too early,there are always somebody might be late.Coach Yehr likes AC sequence very much,the AC sequence is a number sequence with all the elements different.A sequence (S1 ,S2 ,S3 ……Sn ) is a AC sequence if S1 ,S2 ,S3 ……Sn are all different. There are N teammates,the time(in second time) every teammate’arrival make a number sequence with length N. In order to punish the laters,Coach Yehr give them a puzzle,Coach Yehr choose a subsequence from Sa to Sb ,the laters must tell Coach Yehr the longest length of AC sequence in the subsequence as soon as possible.

There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.

There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.

8
3 2 5 6 8 3 2 6
2
2 4
1 8
6
5 3 1 2 3 4
1 6
3 3

3
5
4
2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define maxn 300001
#define eps 1e-6
using namespace std;
int n;
int m;
int len[maxn];
int vis[maxn];
int mx[maxn][24];
int pre[maxn];

int search(int l,int r)
{
int t=l;
while(l<r)
{
int mid=l+r>>1;
if(pre[mid]<t)
{
l=mid+1;
}
else
{
r=mid;
}
}
return l;
}

void init_rmq()
{
int i,j;
int k=(int)(log2(n)+eps);
for(i=1; i<=n; i++)
{
mx[i][0]=len[i];
}
for(i=1; i<=k; i++)
{
for(j=1; j<=n; j++)
{
mx[j][i]=mx[j][i-1];
if(j+(1<<(i-1))<=n)
{
mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
}
}
}
}

int rmq(int l,int r)
{
int k=(int)(log2(r-l+1)+eps);
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}

int main()
{
//freopen("input.txt","r",stdin);
int i,j;
while(scanf("%d",&n)!=EOF)
{
memset(len,0,sizeof(len));
memset(vis,-1,sizeof(vis));
memset(pre,-1,sizeof(pre));
for(i=1; i<=n; i++)
{
int temp;
scanf("%d",&temp);
if(vis[temp]==-1)
{
pre[i]=1;
}
else
{
pre[i]=vis[temp]+1;
}
pre[i]=max(pre[i],pre[i-1]);
len[i]=i-pre[i]+1;
vis[temp]=i;
}
init_rmq();
scanf("%d",&m);
while(m--)
{
int l,r;
scanf("%d %d",&l,&r);
if(l>r) swap(l,r);
int t=search(l,r);
if(t==r)
{
printf("%d\n",t-l+1);
}
else
{
printf("%d\n",max(t-l,rmq(t,r)));
}
}
}
return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。

3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

4. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”