题面
在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为 n 的序列a1,a2,…,an,其中ai为一个正整数，表示第 i 棵蒲公英的种类编号。
而每次询问一个区间 [l,r] ，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。
输入格式
第一行两个整数n，m，表示有 n 株蒲公英，m 次询问。
接下来一行 n 个空格隔开的整数ai,表示蒲公英的种类。
再接下来 m 行每行两个整数l0,r0，我们令上次询问的结果为 x（如果这是第一次询问，则 x=0）。
令l=(l0+x-1) mod n+1,r=(r0+x-1) mod n+1,如果l>r,则交换l，r。
最终的询问区间为[l,r]。
输出格式
输出 m 行。
每行一个整数，表示每次询问的结果。
数据范围
1≤n≤40000,
1≤m≤50000,
1≤ai≤109
输入样例：
6 3
1 2 3 2 1 2
1 5
3 6
1 5
输出样例：
1
2
1
题解
先离散化+预处理 O(nt + nlongn), t为总共的分块数, len为块的大小
当 r - l + 1 >= len * 2 - 1, 则l-r内必有一个整块(包含边界)
1.如果不想麻烦，可以对 r - l + 1 < len * 2 - 1 直接暴力，从 l 到到r，按书上二分方法去查找在l-r直接a[i]的个数，暴力找答案
2.l为块左边界 （l % len == 1）,r为右边界（r % len == 0 || r == n(最后不足一块)）,预处理已经知道答案
3.l为块左边界，找到r 所在块的左边界 rl，预处理知道答案 l-（lr - 1）， 暴力rl - r
3.r为块右边界， 同上
4.分别找 rl 和 lr，预处理知道 (lr + 1) - (rl - 1)的答案，暴力l - rl、 rl - r即可
大概复杂度为 O(nt + m *n * log n / t), 求导 t = （m * n * log(n)）^ (1/3)
#include <bits/stdc++.h>
#define find(x) ((x - 1) / len + 1)
#define wide(l,r) (r - l + 1)
using namespace std;
const int maxn = 4e4 + 5;
const int maxt = 3130;
int len, t, n, m, a[maxn], b[maxn], f[maxt][maxt], tax[maxn], x;
vector<int> ve[maxn];
void init()
{
t = (int)sqrt(n * log2(n));
len = (n - 1) / t + 1;
sort(b + 1, b + 1 + n);
int tot = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1; i <= n; ++ i)
{
a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
ve[a[i]].push_back(i);
}
for (int i = 1; i <= t; ++ i, memset(tax, 0, sizeof tax))
{
int mid = (i - 1) * len + 1;
for (int j = (i - 1) * len + 1; j <= n; ++ j)
{
++ tax[a[j]];
if (mid != a[j])
{
if (tax[mid] < tax[a[j]]) mid = a[j];
else if (tax[mid] == tax[a[j]] && mid > a[j]) mid = a[j];
}
if (j % len == 0 || j == n) f[i][find(j)] = mid;
}
}
}
int get(int l, int r, int k)
{
int ll = lower_bound(ve[k].begin(), ve[k].end(), l) - ve[k].begin();
if (ll == ve[k].size()) return 0;
return upper_bound(ve[k].begin(), ve[k].end(), r) - ve[k].begin() - ll;
}
int work(int cnt, int l, int r, int ll, int rr)
{
for (int j = l, res; j <= r; ++ j)
{
if (x != a[j] || j == l)
{
res = get(ll, rr, a[j]);
if (cnt < res) cnt = res, x = a[j];
else if (cnt == res && x > a[j]) x = a[j];
}
}
return cnt;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i) scanf("%d", a + i), b[i] = a[i];
init();
for (int i = 1, l, r; i <= m; ++ i)
{
scanf("%d%d", &l, &r);
l = (b[x] % n - 1 + l) % n + 1, r = (b[x] % n - 1 + r) % n + 1;
if (l > r) swap(l, r);
if (wide(l, r) < len << 1) work(0, l, r, l, r);
else if (l % len == 1 && (r % len == 0 || r == n)) x = f[find(l)][find(r)];
else if (l % len == 1)
{
int rl = (find(r) - 1) * len + 1;
x = f[find(l)][find(r) - 1];
work(get(l, r, x), rl, r, l, r);
}
else if (r % len == 0)
{
int lr = find(l) * len;
x = f[find(l) + 1][find(r)];
work(get(l, r, x), l, lr, l, r);
}
else
{
int lr = find(l) * len, rl = (find(r) - 1) * len + 1;
x = f[find(l) + 1][find(r) - 1];
work(work(get(l, r, x), l, lr, l, r), rl, r, l, r);
}
printf("%d
", b[x]);
}
return 0;
}