撰写
Description
Download as PDF
The security of many ciphers strongly depends on the fact that the keys are unique and never re-used. This may be vitally important, since a relatively strong cipher may be broken if the same key is used to encrypt several different messages.
In this problem, we will try to detect repeating (duplicate) usage of keys. Given a sequence of keys used to encrypt messages, your task is to determine what keys have been used repeatedly in some specified period.
Input
The input contains several cipher descriptions. Each description starts with one line containing two integer numbers M and Q separated by a space. M(1$ \le$M$ \le$1000000) is the number of encrypted messages, Q is the number of queries (0$ \le$Q$ \le$1000000).
Each of the following M lines contains one number Ki(0$ \le$Ki$ \le$230) specifying the identifier of a key used to encrypt the i-th message. The next Q lines then contain one query each. Each query is specified by two integer numbers Bj and Ej, 1$ \le$Bj$ \le$Ej$ \le$M, giving the interval of messages we want to check.
There is one empty line after each description. The input is terminated by a line containing two zeros in place of the numbers M and Q.
Output
For each query, print one line of output. The line should contain the string “OK” if all keys used to encrypt messages between Bj and Ej (inclusive) are mutually different (that means, they have different identifiers). If some of the keys have been used repeatedly, print one identifier of any such key.
Print one empty line after each cipher description.
Sample Input
10 5
3
2
3
4
9
7
3
8
4
1
1 3
2 6
4 10
3 7
2 6
5 2
1
2
3
1
2
2 4
1 5
0 0
Sample Output
3
OK
4
3
OK
OK
1
题意：询问m次区间内是否有重复的数，有则任意输出一个，没有则ok
题解：一开始用了莫队算法，理论上是可以的，但是队友好像改错了哈哈哈哈哈
实际上，只要进行一个预处理，用f[i]记录从i~n位置第一个出现重复的数的位置。
预处理从后往前扫，用一个map表示上一个a[i]的位置，则f[i] = min(m[a[i]],b[i]);//(b[i]=b[i+1]）//a[i]可能出现也可能未出现过，所以要判断min
代码
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define PB push_back
#define MP make_pair
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
#define PI acos(-1.0)
#define INF 0x7FFFFFFF
#define LINF 1000000000000000000LL
#define eps 1e-8
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+100;
int n,m;
int a[maxn];
int b[maxn];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n && !m) break;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
map<int ,int > p;
p.clear();
CLR(b);
for(int i=n-1;i>=0;i--)
{
b[i]=INF;
if(i<n-1) b[i]=b[i+1];
if(p.find(a[i])!=p.end())
b[i]=min(b[i],p[a[i]]);
p[a[i]]=i;
}
int l,r;
for(int i=0;i<m;i++)
{
scanf("%d%d",&l,&r);
l--,r--;
if(b[l]<=r)
printf("%d\n",a[b[l]]);
else
printf("OK\n");
}
cout<<endl;
}
return 0;
}