You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
98 lines
3.2 KiB
C++
98 lines
3.2 KiB
C++
#include <algorithm>
|
|
#include <cctype>
|
|
#include <cmath>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
inline void read(int &x)
|
|
{
|
|
int ch = x = 0;
|
|
while (!isdigit(ch)) ch = getchar();
|
|
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
|
|
}
|
|
const int B = 205, N = B * B, inf = 0x3f3f3f3f;
|
|
int n, q, S, bcnt, a[N], b[N], cnt[N][B], f[B][B], cnt2[N], vis[N];
|
|
bool isR[N];
|
|
int main()
|
|
{
|
|
memset(vis, -1, sizeof(vis));
|
|
read(n), read(q), S = (int)sqrt(n);
|
|
for (int i = 0; i < n; i++) read(a[i]);
|
|
memcpy(b, a, n << 2);
|
|
std::sort(b, b + n);
|
|
int m = int(std::unique(b, b + n) - b);
|
|
for (int i = 0; i < n; i++) a[i] = int(std::lower_bound(b, b + m, a[i]) - b);
|
|
for (int i = 0, bidx = 0; i < n; i++, bidx++)
|
|
{
|
|
if (bidx == S) bidx = 0, bcnt++, isR[i - 1] = true;
|
|
cnt[a[i]][bcnt]++;
|
|
}
|
|
isR[n - 1] = true;
|
|
bcnt = n / S + (n % S > 0);
|
|
for (int i = 0; i < n; i++)
|
|
for (int j = 1; j < bcnt; j++)
|
|
cnt[i][j] += cnt[i][j - 1];
|
|
for (int i = 0; i < bcnt; i++)
|
|
{
|
|
memset(cnt2, 0, sizeof(cnt2));
|
|
for (int j = i * S, tans = 0; j < n; j++)
|
|
{
|
|
cnt2[a[j]]++;
|
|
if (cnt2[a[j]] > cnt2[tans] || (cnt2[a[j]] == cnt2[tans] && a[j] < tans)) tans = a[j];
|
|
if (isR[j]) f[i][j / S] = tans;
|
|
}
|
|
}
|
|
int ans = 0, l, r;
|
|
while (q--)
|
|
{
|
|
read(l), read(r);
|
|
l = (l + ans - 1) % n, r = (r + ans - 1) % n;
|
|
if (l > r) std::swap(l, r);
|
|
if (r - l < S * 2)
|
|
{
|
|
int tans = N - 1, tcnt = -1;
|
|
for (int i = l; i <= r; i++)
|
|
{
|
|
if (vis[a[i]] != q) vis[a[i]] = q, cnt2[a[i]] = 0;
|
|
cnt2[a[i]]++;
|
|
if (cnt2[a[i]] > tcnt || (cnt2[a[i]] == tcnt && a[i] < tans))
|
|
tcnt = cnt2[tans = a[i]];
|
|
}
|
|
printf("%d\n", ans = b[tans]);
|
|
}
|
|
else
|
|
{
|
|
int bl = l / S, br = r / S;
|
|
int bll = bl * S, brr = (br + 1) * S - 1;
|
|
if (brr >= n) brr = n - 1;
|
|
if (l > bll) bll = (++bl) * S;
|
|
if (r < brr) brr = (--br + 1) * S - 1;
|
|
int curAns = f[bl][br];
|
|
int curAnsCnt = cnt[curAns][br];
|
|
if (bl > 0) curAnsCnt -= cnt[curAns][bl - 1];
|
|
for (int i = l; i < bll; i++)
|
|
{
|
|
if (vis[a[i]] != q)
|
|
{
|
|
vis[a[i]] = q, cnt2[a[i]] = cnt[a[i]][br];
|
|
if (bl > 0) cnt2[a[i]] -= cnt[a[i]][bl - 1];
|
|
}
|
|
cnt2[a[i]]++;
|
|
if (cnt2[a[i]] > curAnsCnt || (cnt2[a[i]] == curAnsCnt && a[i] < curAns))
|
|
curAnsCnt = cnt2[curAns = a[i]];
|
|
}
|
|
for (int i = r; i > brr; i--)
|
|
{
|
|
if (vis[a[i]] != q)
|
|
{
|
|
vis[a[i]] = q, cnt2[a[i]] = cnt[a[i]][br];
|
|
if (bl > 0) cnt2[a[i]] -= cnt[a[i]][bl - 1];
|
|
}
|
|
cnt2[a[i]]++;
|
|
if (cnt2[a[i]] > curAnsCnt || (cnt2[a[i]] == curAnsCnt && a[i] < curAns))
|
|
curAnsCnt = cnt2[curAns = a[i]];
|
|
}
|
|
printf("%d\n", ans = b[curAns]);
|
|
}
|
|
}
|
|
return 0;
|
|
} |