算法竞赛进阶指南， 227页，分块, 离散化
本题要点：
1、先离散化，编号的大小为 10^9, 而元素个数为 5 * 10^5
2、 分块，将 n 个数值，平均分为 sqrt(n * log(n)) 段。 f[i][j]表示从第i段到第j段，出现最多的蒲公英编号。
3、数组 f[T][T]的计算，详细看代码。
4、 假如区间 [l ,r] 包含3 部分，中间是若干完整的段 [L, R]，两边是不完整的段 [l, L), (R, r] ,
那么中间部分，直接得到出现最多的是哪个编号（f[L][R]）， 并计算出其出现过的次数。
扫描左右两边的两个不完整段，所有出现过的编号，计算每一个编号出现过的次数。
取以上出现过的最多次数，就是答案。
5、 计算某个编号 x 在 区间 [l, r] 出现的次数：
在序列 e[x] 中查找第一个大于等于l 的下标 ，lower_bound(e[x].begin(), e[x].end(), l);
在序列 e[x] 中查找第一个大于r 的下标, upper_bound(e[x].begin(), e[x].end(), r);
两个值相减即可;
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 40006, T = 806;
int a[N], b[N], c[N], L[N], R[N], pos[N], f[T][T];
//L[N], R[N]分别表示每一段的左端点，右端点; pos[i] 表示 点i所在的段的编号
// f[i][j]表示从第i段到第j段，出现最多的蒲公英编号
vector<int> e[N]; // e[i]表示数值i 在序列中出现的下标
int n, m, t;void discrete()
{
memcpy(b, a, sizeof b);sort(b + 1, b + n + 1);int tot = unique(b + 1, b + n + 1) - (b + 1);for(int i = 1; i <= n; ++i){
a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;e[a[i]].push_back(i);}
}int Find(int x, int l, int r)
{
return upper_bound(e[x].begin(), e[x].end(), r) - lower_bound(e[x].begin(), e[x].end(), l);
}void work(int x, int l, int r, int &ans, int &cnt)
{
int w = Find(x, l, r);if(w > cnt || (w == cnt && x < ans)){
cnt = w, ans = x;}
}int ask(int l, int r)
{
int p = pos[l], q = pos[r];int ans = 0, cnt = 0;if(p == q) //属于同一段{
for(int i = l; i <= r; ++i){
work(a[i], l, r, ans, cnt);}return b[ans];}int x = 0, y = 0;if(p + 1 <= q - 1){
x = p + 1, y = q - 1;}for(int i = l; i <= R[p]; ++i){
work(a[i], l, r, ans, cnt);}for(int i = L[q]; i <= r; ++i){
work(a[i], l, r, ans, cnt); }if(f[x][y]){
work(f[x][y], l, r, ans, cnt);}return b[ans];
}int main()
{
scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);}discrete();t = sqrt(log(n) / log(2) * n); //一共有t段int len = t ? n / t : n; //每一段的长度for(int i = 1; i <= t; ++i){
L[i] = (i - 1) * len + 1;R[i] = i * len;}if(R[t] < n){
++t, L[t] = R[t - 1] + 1, R[t] = n;}for(int i = 1; i <= t; ++i)for(int j = L[i]; j <= R[i]; ++j){
pos[j] = i; //坐标 j所在哪一段}memset(f, 0, sizeof f);for(int i = 1; i <= t; ++i) {
memset(c, 0, sizeof c); //数组c[i] 表示数值i出现的次数int cnt = 0, ans = 0; //cnt 表示出现的次数，ans表示这个数是多少for(int j = L[i]; j <= n; ++j){
if(++c[a[j]] > cnt || (c[a[j]] == cnt && a[j] < ans)){
cnt = c[a[j]];ans = a[j];}f[i][pos[j]] = ans;}}int left, right, x = 0;while(m--){
scanf("%d%d", &left, &right);left = (left + x - 1) % n + 1;right = (right + x -1) % n + 1;if(left > right) swap(left, right);x = ask(left, right);printf("%d\n", x);}return 0;
}/* 6 3 1 2 3 2 1 2 1 5 3 6 1 5 *//* 1 2 1 */