题解 P4168 【[Violet]蒲公英】
# 本篇题解的分块思路并不需要二分
首先把区间分块， 预处理出每个块内每个数出现的次数， 以及区间众数，然后把所有连续的块的众数求出来，预处理是 O(NT^2),这里的T是把区间分成的块数，同时查询的时候，可以再进行一次朴素的扫描， 把块两边余处的地方经行处理即可复杂度为O(MN/T);
所以综上复杂度为O(NT^2 + MN/T), 通过一定的计算可的， 最有复杂度应该在NT^2 = MN/T时取得， 我们假设N和M是同数量级的， 即NT^2 = N^2/T, 可得当T =（N ^(1/ 3))时可以有最有的复杂度O(N^(5/3))!
同时我们在时间复杂度最优的情况下空间为O(NT^2), 即O(N^(5/3))， 可以通过本题！
同时推荐徐明宽神仙的论文《非常规大小分块算法初探》 QwQ
ps:那么问题来了，如果不算一下分块大小会怎么样？然而我们这样写挂了，不但炸了空间，导致要开一个数量级1e9的数组，要不就会RE + 各种TLE,所以不能只要分块题都随手开根号啊！可以自己算一下， 简单的话均值不等式就可以解决大部分的分块大小问题了!
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 40005;
inline int read() {
int x = 0; char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c<='9'){x = x * 10 + c - 48; c = getchar();}
return x;
}
int sum[50][50][N], f[50][50], Cnt[50][50];
int K, n, m, bl[N], blo, a[N], b[N];
inline int query(int l, int r) {
int ans = 0, cnt = 0x3f3f3f3f;
if(l > r) swap(l, r);
int L = bl[l], R = bl[r];
if(L == R) {
L = R = 0;
for(int i = l; i <= r; i ++) {
sum[L][R][a[i]] ++;
if(sum[L][R][a[i]] > ans || sum[L][R][a[i]] == ans && a[i] < cnt)
cnt = a[i], ans = sum[L][R][a[i]];
}
for(int i = l; i <= r; i ++)
sum[L][R][a[i]] --;
return b[cnt];
}
else L = L + 1, R = R - 1;
ans = f[L][R], cnt = Cnt[L][R];
for(int i = l; i <= min((L - 1) * blo, r); i ++) {
sum[L][R][a[i]] ++;
if(sum[L][R][a[i]] > ans || (sum[L][R][a[i]] == ans && a[i] < cnt)) {
cnt = a[i], ans = sum[L][R][a[i]];
}
}
for(int i = R * blo + 1; i <= r; i ++) {
sum[L][R][a[i]] ++;
if(sum[L][R][a[i]] > ans || sum[L][R][a[i]] == ans && a[i] < cnt) {
cnt = a[i], ans = sum[L][R][a[i]];
}
}
for(int i = R * blo + 1; i <= r; i ++)
sum[L][R][a[i]] --;
for(int i = l; i <= min((L - 1) * blo, r); i ++)
sum[L][R][a[i]] --;
return b[cnt];
}
int main() {
// freopen("tjj.in", "r" ,stdin);
n = read(), m = read();
for(int i = 1; i <= n; i ++)
a[i] = read(), b[i] = a[i];
sort(b + 1, b + n + 1);
K = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; i ++)
a[i] = lower_bound(b + 1, b + K + 1, a[i]) - b;
blo = pow(n * 1.0, 1.0/ 3);
if(blo!=0) blo = n/blo;
else blo = 1;
for(int i = 1; i <= n; i ++)
bl[i] = (i - 1) / blo + 1;
for(int i = 1; i <= bl[n]; i ++) {
for(int j = i; j <= bl[n]; j ++) {
for(int k = (i - 1) * blo + 1; k <= min(blo * j, n); k ++)
sum[i][j][a[k]] ++;
for(int k = 1; k <= K; k ++)
if(sum[i][j][k] > f[i][j])
f[i][j] = sum[i][j][k], Cnt[i][j] = k;
}
}
int ans = 0;
for(int i = 1; i <= m; i ++) {
int x = read(), y = read();
ans = query((x + ans - 1) % n + 1, (y + ans - 1) % n + 1);
printf("%d\n", ans);
}
}