bzoj#P3489. A simple rmq problem

A simple rmq problem

题目描述

给出一个长度为 nn 的序列,给出 mm 个询问:在 [l,r][l,r] 之间找到一个在这个区间里 只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出 00。强制在线。

输入格式

输入第一行为两个整数 n,mn, m. nn 是序列长度, mm 是询问数.

第二行为 nn 个整数, 描述这个序列 {ai}\{ a_i\}.

接下来 mm 行, 每行两个整数 x,yx, y. 询问区间 [l,r][l,r] 由下列规则产生:

$l=min((x+lastans)mod \ n+1,(y+lastans) mod \ n+1)$

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

lastanslastans 表示上一个询问的答案,一开始 lastanslastans00.

输出格式

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

样例输入

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

n105,m2×105n \leq 10^5, m \leq 2 \times 10^5