题意
给定序列 \(s\)，求 \(l, r\) 的区间众数，强制在线。
Sol
考虑分块。
不难想到可以预处理出块 \(l\) 到块 \(r\) 的区间众数。
然后查询时将散块出现的数在整块中出现的个数加入贡献。
这个玩意可以用前缀和简单预处理。
然后就做完了。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <queue>
#include <vector>
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5, M = 505;
array <int, N> s, h;
namespace Blk {
int bsi = 332;
int calc(int x) {
return (x - 1) / bsi + 1;
}
array <array <int, N>, M> pre;
array <array <pii, M>, M> suf;
array <int, N> cur;
queue <int> q;
int tot;
void add(int x, int y) {
if (!x) return;
cur[x] += y;
q.push(x);
if (cur[x] > cur[tot]) tot = x;
else if (cur[x] == cur[tot]) tot = min(tot, x);
}
void clear() {
while (!q.empty())
cur[q.front()] = 0, q.pop();
tot = 0;
}
void init(int n) {
for (int i = 1; i <= calc(n); i++) {
for (int j = i; j <= calc(n); j++) {
for (int k = (j - 1) * bsi + 1; k <= min(j * bsi, n); k++)
add(s[k], 1);
/* write(tot), puts(""); */
suf[i][j] = make_pair(tot, cur[tot]);
}
clear();
}
for (int i = 1; i <= calc(n); i++) {
for (int k = (i - 1) * bsi + 1; k <= min(i * bsi, n); k++)
add(s[k], 1);
pre[i] = cur;
}
clear();
}
int query(int x, int y) {
int ans = 0;
if (calc(x) == calc(y)) {
for (int i = x; i <= y; i++)
add(s[i], 1);
ans = tot; clear();
return ans;
}
vector <int> tp;
int l = calc(x), r = calc(y) - 1;
for (int i = x; i <= calc(x) * bsi; i++)
add(s[i], 1), tp.push_back(s[i]);
/* write(cur[2]), puts("%%"); */
add(suf[l + 1][r].fi, suf[l + 1][r].se);
for (int i = (calc(y) - 1) * bsi + 1; i <= y; i++)
add(s[i], 1), tp.push_back(s[i]);
/* write(cur[2]), puts("%%"); */
sort(tp.begin(), tp.end());
tp.erase(unique(tp.begin(), tp.end()), tp.end());
for (auto k : tp) {
if (k == suf[l + 1][r].fi) continue;
add(k, pre[r][k] - pre[l][k]);
}
/* write(cur[2]), puts("%%"); */
ans = tot; clear();
return ans;
}
}
int main() {
/* freopen("P4168_2.in", "r", stdin); */
int n = read(), m = read();
for (int i = 1; i <= n; i++)
s[i] = h[i] = read();
sort(h.begin() + 1, h.begin() + 1 + n);
int k = unique(h.begin() + 1, h.begin() + 1 + n) - h.begin() - 1;
for (int i = 1; i <= n; i++)
s[i] = lower_bound(h.begin() + 1, h.begin() + 1 + k, s[i]) - h.begin();
/* for (int i = 1; i <= k; i++) */
/* write(h[i]), putchar(32); */
/* puts(""); */
/* write(k), puts("######"); */
Blk::init(n);
int lst = 0;
/* write(Blk::tot), puts("@"); */
/* for (int i = 1; i <= n; i++) { */
/* if (s[i] == 2) lst++; */
/* } */
/* write(lst), puts(""); */
/* write(Blk::cur[2]), puts(""); */
/* return 0; */
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
l = (lst + l - 1) % n + 1, r = (lst + r - 1) % n + 1;
if (l > r) swap(l, r);
/* write(lst = h[Blk::query(l, r)]), puts(""); */
lst = h[Blk::query(l, r)];
int now = 0;
/* for (int i = Blk::calc(l) * Blk::bsi + 1; i <= (Blk::calc(r) - 1) * Blk::bsi; i++) */
/* if (h[s[i]] == 1183190) now++; */
/* write(Blk::calc(l) * Blk::bsi + 1), putchar(32); */
/* write((Blk::calc(r) - 1) * Blk::bsi), putchar(32); */
/* write(now), puts(""); */
write(lst), puts("");
/* if (i == 2) break; */
}
return 0;
}