F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 3489. -- A simple rmq problem

3489: A simple rmq problem

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 3006  Solved: 1020
[Submit][Status][Discuss]

Description

因为是OJ上的题,就简单点好了。给出一个长度为n的序列,给出M个询问:在[l,r]之间找到一个在这个区间里只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出0。我会采取一些措施强制在线。

 

Input

第一行为两个整数N,MM是询问数,N是序列的长度(N<=100000M<=200000)

第二行为N个整数,描述这个序列{ai},其中所有1<=ai<=N

再下面M行,每行两个整数xy

询问区间[l,r]由下列规则产生(OIER都知道是怎样的吧>_<)

l=min(x+lastans)mod n+1,(y+lastansmod n+1);

r=max(x+lastans)mod n+1,(y+lastansmod n+1);

Lastans表示上一个询问的答案,一开始lastans0

Output

一共M行,每行给出每个询问的答案。

Sample Input

10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9

Sample Output

4
10
10
0
0
10
0
4
0
4

HINT



注意出题人为了方便,input的第二行最后多了个空格。


2015.6.24新加数据一组,2016.7.9放至40S,600M,但未重测


 

Source

by zhzqkkk

[Submit][Status][Discuss]

HOME Back