题目的意思是给你从1-M区间的数值,接下来有m次询问,每次询问l、r区间,问个区间是否有相同的数,若没有,则输出OK、否则输出任意一个相同的数。

这个题目有点坑。明明说了是any,但是却没有特判,只能找区间内最左边的那个相同的数。还有就是一个空行的问题,坑!


但是这题非常有意思,本来我是记录离当前值最近的那个数的位置,但是却WA了,可能是TLE但是显示了WA。然后发现有更好的思维。

可以从最右边开始循环,记录离当前值最近有重复的值的位置,这样就能把时间复杂度降到n。


题目地址:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3892


代码:

StatusAccepted
Time1868ms
Length672
LangC++11 5.3.0


#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=1000005;
int data[maxn], last[maxn];
int m, q, l, r;
map<int,int> key;
int main()
{
    while(scanf("%d%d", &m, &q)&&m+q){
        key.clear();
        for(int i=1;i<=m;i++)scanf("%d", &data[i]);
        last[m+1]=m+1;
        for(int i=m;i>0;i--){
            last[i]=last[i+1];
            if(key[data[i]])last[i]=min(last[i], key[data[i]]);
            key[data[i]]=i;
        }
        while(q--){
            scanf("%d%d", &l, &r);
            if(last[l]<=r)printf("%d\n", data[last[l]]);
            else printf("OK\n");
        }
        printf("\n");
    }
    return 0;
}