乍一看不会。
想了想，求出每一个数的前一个相同的数的位置和后一个相同的数的位置，然后询问就是L<=i<=R && next[i]>=R && last[i] <= L的最大的a[i]。这三层树套树啊！？
好像不带修改，那可以把一个Log的树优化成1的前缀和。
然后最值不满足减法，所以就把L<=i<=R拿动态建的线段树套里面好了。
卡空间400+MB过了，我对拍的大数据把网上的某人的程序干掉了哈哈。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct seg {
int v, ls, rs;
};
const int maxn = 100009;
const int maxnd = maxn * 409;
int n, m, a[maxn], v[maxn], ls[maxn], nx[maxn], o[maxn];
int t[maxn], sp;
seg sl[maxnd];
inline bool cmpO(const int& a, const int& b) {
return ls[a] < ls[b];
}
int getLa(int l0) {
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ls[o[mid]] < l0)
l = mid;
else
r = mid - 1;
}
return l;
}
#define vof(p) ((p)?(sl[p].v):0)
#define lson(p) ((p)?(sl[p].ls):0)
#define rson(p) ((p)?(sl[p].rs):0)
int sgtIns(int q, int p0, int v0) {
int s = ++ sp, p = s;
int l = 1, r = n;
while (l < r) {
sl[p]. v = max(vof(q), v0);
int mid = (l + r) >> 1;
if (p0 <= mid) {
sl[p]. rs = rson(q);
q = lson(q);
sl[p]. ls = ++ sp;
p = lson(p);
r = mid;
}
else {
sl[p]. ls = lson(q);
q = rson(q);
sl[p]. rs = ++ sp;
p = rson(p);
l = mid + 1;
}
}
sl[p]. v = max(v0, vof(q));
sl[p]. ls = 0;
sl[p]. rs = 0;
return s;
}
int psgtIns(int q, int p0, int v0, int v1) {
int s = ++ sp, p = s;
int l = 1, r = n + 1;
while (l < r) {
sl[p]. v = sgtIns(vof(q), v0, v1);
int mid = (l + r) >> 1;
if (p0 <= mid) {
sl[p]. rs = rson(q);
q = lson(q);
sl[p]. ls = ++ sp;
p = lson(p);
r = mid;
}
else {
sl[p]. ls = lson(q);
q = rson(q);
sl[p]. rs = ++ sp;
p = rson(p);
l = mid + 1;
}
}
sl[p]. v = sgtIns(vof(q), v0, v1);
sl[p]. ls = 0;
sl[p]. rs = 0;
return s;
}
int sgtQry(int p, int l, int r, int pl, int pr) {
if (!p)
return 0;
else if (l == pl && r == pr)
return vof(p);
else {
int mid = (pl + pr) >> 1;
if (r <= mid)
return sgtQry(lson(p), l, r, pl, mid);
else if (l >= mid + 1)
return sgtQry(rson(p), l, r, mid + 1, pr);
else
return max(sgtQry(lson(p), l, mid, pl, mid), sgtQry(rson(p), mid + 1, r, mid + 1, pr));
}
}
int psgtQry(int p, int l0, int r0) {
int ans = 0;
int l = 1, r = n + 1;
while (l < r && p) {
int mid = (l + r) >> 1;
if (mid >= r0) {
ans = max(ans, sgtQry(vof(rson(p)), l0, r0, 1, n));
r = mid;
p = lson(p);
}
else {
l = mid + 1;
p = rson(p);
}
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
memset(v, 0, sizeof(v));
memset(t, 0, sizeof(t));
for (int i = 1; i <= n; ++ i) {
scanf("%d", a + i);
ls[i] = v[a[i]];
v[a[i]] = i;
}
for (int i = 1; i <= n; ++ i)
v[i] = n + 1;
for (int i = n; i; -- i) {
nx[i] = v[a[i]];
v[a[i]] = i;
o[i] = i;
}
sp = 0;
sort(o + 1, o + 1 + n, cmpO);
t[0] = 0;
for (int i = 1; i <= n; ++ i)
t[i] = psgtIns(t[i - 1], nx[o[i]], o[i], a[o[i]]);
int lans = 0;
while (m --) {
int l, r;
scanf("%d%d", &l, &r);
l = (l + lans) % n + 1;
r = (r + lans) % n + 1;
if (l > r)
swap(l, r);
int x = getLa(l);
printf("%d\n", (lans = psgtQry(t[x], l, r)));
}
}