prow2012-A3-0007

从 Trac 迁移的文章

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

原文章内容如下：

题意：给出一串长度为N的序列，给出M组询问，每组询问一段[l,r]区间内的重复情况，如有输出最后一组重复的数字，否者输出OK. 

用类似正向表建立的方法，标识出每个数字最后一次出现位置，这样可以dp每个位置，得到最迟一次发现一对重复数字的位置在哪。

查询的时候，比较右端点的DP值和左端点，就能判断是否区间内有重复。


{{{

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
map<int,int> pos;
int L[50100],R[50100],ans[50100],order[50100];
int pre[501000],A[501000],f[501000];

int main(){
    int i,N,M;
    while(scanf("%d",&N)!=EOF){
        pos.clear();

        f[0] = 0;
        for (i=1;i<=N;i++)
        {
            scanf("%d",&A[i]);
            pre[i] = pos[A[i]];
            pos[A[i]] = i;
            f[i] = max(f[i-1],pre[i]);
        }
        scanf("%d",&M);
        for (i=0;i<M;i++)
        {
            scanf("%d%d",&L[i],&R[i]);
            if (f[R[i]]>=L[i]) printf("%d\n",A[f[R[i]]]);
            else printf("OK\n");
        }

        printf("\n");
    }
}

}}}

题意：给出一串长度为N的序列，给出M组询问，每组询问一段[l,r]区间内的重复情况，如有输出最后一组重复的数字，否者输出OK.

用类似正向表建立的方法，标识出每个数字最后一次出现位置，这样可以dp每个位置，得到最迟一次发现一对重复数字的位置在哪。

查询的时候，比较右端点的DP值和左端点，就能判断是否区间内有重复。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
map<int,int> pos;
int L[50100],R[50100],ans[50100],order[50100];
int pre[501000],A[501000],f[501000];
int main(){
    int i,N,M;
    while(scanf("%d",&N)!=EOF){
        pos.clear();
        f[0] = 0;
        for (i=1;i<=N;i++)
        {
            scanf("%d",&A[i]);
            pre[i] = pos[A[i]];
            pos[A[i]] = i;
            f[i] = max(f[i-1],pre[i]);
        }
        scanf("%d",&M);
        for (i=0;i<M;i++)
        {
            scanf("%d%d",&L[i],&R[i]);
            if (f[R[i]]>=L[i]) printf("%d\n",A[f[R[i]]]);
            else printf("OK\n");
        }
        printf("\n");
    }
}