bzoj#P3489. A simple rmq problem
A simple rmq problem
题目描述
给出一个长度为 的序列,给出 个询问:在 之间找到一个在这个区间里 只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出 。强制在线。
输入格式
输入第一行为两个整数 . 是序列长度, 是询问数.
第二行为 个整数, 描述这个序列 .
接下来 行, 每行两个整数 . 询问区间 由下列规则产生:
$l=min((x+lastans)mod \ n+1,(y+lastans) mod \ n+1)$
表示上一个询问的答案,一开始 为 .
输出格式
一共 行,每行给出每个询问的答案。
样例输入
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
样例输出
4
10
10
0
0
10
0
4
0
4
数据范围
时间限制应调整为共 40s, 空间限制 600 MB