题目的意思是给你从1-M区间的数值,接下来有m次询问,每次询问l、r区间,问个区间是否有相同的数,若没有,则输出OK、否则输出任意一个相同的数。
这个题目有点坑。明明说了是any,但是却没有特判,只能找区间内最左边的那个相同的数。还有就是一个空行的问题,坑!
但是这题非常有意思,本来我是记录离当前值最近的那个数的位置,但是却WA了,可能是TLE但是显示了WA。然后发现有更好的思维。
可以从最右边开始循环,记录离当前值最近有重复的值的位置,这样就能把时间复杂度降到n。
题目地址:
代码:
Status | Accepted |
---|---|
Time | 1868ms |
Length | 672 |
Lang | C++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; }