laekov

乍一看不会。

想了想，求出每一个数的前一个相同的数的位置和后一个相同的数的位置，然后询问就是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)));

}

}