【题解】A simple RMQ problem
占坑，免得咕咕咕了，争取在2h内写出代码
upd:由于博主太菜而且硬是要用指针写两个主席树，所以延后2hQAQ
upd:由于博主太菜而且太懒所以他决定写kd tree了
upd:由于博主太菜而且太懒所以他不写代码了(实际上是写了6k之后崩溃了)
所以直接口胡题解
题目大意：
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
好就是这样
解法:
我本来是想直接对值域线段树可持久化，然后类似于吉司机线段树一样维护最小值和次小值...发现不会查一个区间，于是我们可以这样：
每个位置记录i一个上一次出现的(pre)和下一次出现的(next)，把所有数先按照(pre)从小往大排序，对于每一个位置，维护一个数组，数组的下标是next[i]，数组里面的值是data[i]，查询的时候查询查询这个数组([r+1,n+1])中的最大值是多少，就是我们的答案。可持久化数组可以用主席树维护，前缀(pre)的(next)可以用主席树维护，所以只要主席树套主席树就(ok)了。
时空复杂度(O(n log^2 n))
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline void Read(int &Num) {
char c = getchar();
bool Neg = false;
while (c < '0' || c > '9') {
if (c == '-')
Neg = true;
c = getchar();
}
Num = c - '0';
c = getchar();
while (c >= '0' && c <= '9') {
Num = Num * 10 + c - '0';
c = getchar();
}
if (Neg)
Num = -Num;
}
inline int gmin(int a, int b) { return a < b ? a : b; }
inline int gmax(int a, int b) { return a > b ? a : b; }
const int MaxN = 100000 + 5, MaxNodeI = 2000000 + 5, MaxNodeII = 40000000 + 5;
int n, m, Ans, IndexI, IndexII;
int Last[MaxN], Root_I[MaxN], Son_I[MaxNodeI][2], Root_II[MaxNodeI], Son_II[MaxNodeII][2], T[MaxNodeII];
struct ES {
int Pos, Num, Prev, Next;
bool operator<(const ES &b) const { return Prev < b.Prev; }
bool operator<(const int &b) const { return Prev < b; }
} E[MaxN];
void Insert_II(int &x, int Last, int s, int t, int Pos, int Num) {
if (x == 0)
x = ++IndexII;
T[x] = gmax(T[Last], Num);
if (s == t)
return;
int m = (s + t) >> 1;
if (Pos <= m) {
Son_II[x][1] = Son_II[Last][1];
Insert_II(Son_II[x][0], Son_II[Last][0], s, m, Pos, Num);
} else {
Son_II[x][0] = Son_II[Last][0];
Insert_II(Son_II[x][1], Son_II[Last][1], m + 1, t, Pos, Num);
}
}
void Insert_I(int &x, int Last, int s, int t, int Nxt, int Pos, int Num) {
if (x == 0)
x = ++IndexI;
Insert_II(Root_II[x], Root_II[Last], 0, n + 1, Pos, Num);
if (s == t)
return;
int m = (s + t) >> 1;
if (Nxt <= m) {
Son_I[x][1] = Son_I[Last][1];
Insert_I(Son_I[x][0], Son_I[Last][0], s, m, Nxt, Pos, Num);
} else {
Son_I[x][0] = Son_I[Last][0];
Insert_I(Son_I[x][1], Son_I[Last][1], m + 1, t, Nxt, Pos, Num);
}
}
int Get_II(int x, int s, int t, int l, int r) {
if (x == 0)
return 0;
if (l <= s && r >= t)
return T[x];
int ret = 0, m = (s + t) >> 1;
if (l <= m)
ret = gmax(ret, Get_II(Son_II[x][0], s, m, l, r));
if (r >= m + 1)
ret = gmax(ret, Get_II(Son_II[x][1], m + 1, t, l, r));
return ret;
}
int Get_I(int x, int s, int t, int l_I, int r_I, int l_II, int r_II) {
if (x == 0)
return 0;
if (l_I <= s && r_I >= t)
return Get_II(Root_II[x], 0, n + 1, l_II, r_II);
int ret = 0, m = (s + t) >> 1;
if (l_I <= m)
ret = gmax(ret, Get_I(Son_I[x][0], s, m, l_I, r_I, l_II, r_II));
if (r_I >= m + 1)
ret = gmax(ret, Get_I(Son_I[x][1], m + 1, t, l_I, r_I, l_II, r_II));
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
Read(E[i].Num);
E[i].Pos = i;
E[i].Prev = Last[E[i].Num];
E[E[i].Prev].Next = i;
E[i].Next = n + 1;
Last[E[i].Num] = i;
}
sort(E + 1, E + n + 1);
for (int i = 1; i <= n; ++i) Insert_I(Root_I[i], Root_I[i - 1], 0, n + 1, E[i].Next, E[i].Pos, E[i].Num);
Ans = 0;
int x, y, l, r, p;
for (int i = 1; i <= m; ++i) {
Read(x);
Read(y);
l = gmin((x + Ans) % n + 1, (y + Ans) % n + 1);
r = gmax((x + Ans) % n + 1, (y + Ans) % n + 1);
p = lower_bound(E + 1, E + n + 1, l) - E - 1;
Ans = Get_I(Root_I[p], 0, n + 1, r + 1, n + 1, l, r);
printf("%d
", Ans);
}
return 0;
}