2012-0007

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

先对输入数字进行hash处理
尾指针一开始处于位置1
头指针正向扫描数列，如果头指针指向的当前数字在之前出现过（in[ a[head] ]=true)，
则令尾指针不停加一，并且使 in[ a[tail] ]变为false，直到in[ a[head] ]=false为止，
可以发现此时tail指针所在位置，就是当前数字之前一次在数列中出现过的位置，令pos[head]=tail即可
pos[i]表示对于以第i个位置结尾的区间来说，所求答案所在的位置。     时间复杂度:O(n)                                  ————————By kotori
{{{
#include<stdio.h>
#include<cstring>
#include<map>
#define maxn 524288
using namespace std;
int a[maxn],pos[maxn];
int link[maxn];
bool in[maxn];
int n,m,beg,end;
map<int,int>hash;
int main()
{
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  int i,j,tmp;
  while(scanf("%d",&n)!=EOF){
    memset(pos,0,sizeof(pos));
    memset(in,0,sizeof(in));
    memset(link,0,sizeof(link));
    hash.clear();
    tmp=0;
    for(i=1;i<=n;i++){
      scanf("%d",&j);
      if(hash[j]==0){
        hash[j]=++tmp;
        link[tmp]=j;
      }
      a[i]=hash[j];
    }
    for(i=1,j=0;i<=n;i++){
      if(in[a[i]])
        while(in[a[i]])
          in[a[++j]]=0;
      pos[i]=j;
      in[a[i]]=1;
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++){
      scanf("%d%d",&beg,&end);
      if(pos[end]<beg)
        printf("OK\n");
      else
        printf("%d\n",link[ a[pos[end]] ]);
    }
    printf("\n");
  }
  return 0;
}
}}}

先对输入数字进行hash处理

尾指针一开始处于位置1

头指针正向扫描数列，如果头指针指向的当前数字在之前出现过（in[ a[head] ]=true)，

则令尾指针不停加一，并且使 in[ a[tail] ]变为false，直到in[ a[head] ]=false为止，

可以发现此时tail指针所在位置，就是当前数字之前一次在数列中出现过的位置，令pos[head]=tail即可

pos[i]表示对于以第i个位置结尾的区间来说，所求答案所在的位置。 时间复杂度:O(n) ————————By kotori

#include<stdio.h>
#include<cstring>
#include<map>
#define maxn 524288
using namespace std;
int a[maxn],pos[maxn];
int link[maxn];
bool in[maxn];
int n,m,beg,end;
map<int,int>hash;
int main()
{
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  int i,j,tmp;
  while(scanf("%d",&n)!=EOF){
    memset(pos,0,sizeof(pos));
    memset(in,0,sizeof(in));
    memset(link,0,sizeof(link));
    hash.clear();
    tmp=0;
    for(i=1;i<=n;i++){
      scanf("%d",&j);
      if(hash[j]==0){
        hash[j]=++tmp;
        link[tmp]=j;
      }
      a[i]=hash[j];
    }
    for(i=1,j=0;i<=n;i++){
      if(in[a[i]])
        while(in[a[i]])
          in[a[++j]]=0;
      pos[i]=j;
      in[a[i]]=1;
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++){
      scanf("%d%d",&beg,&end);
      if(pos[end]<beg)
        printf("OK\n");
      else
        printf("%d\n",link[ a[pos[end]] ]);
    }
    printf("\n");
  }
  return 0;
}