题目链接

#include <bits/stdc++.h>
#define int long long
#define reg register
using namespace std;
template<typename T> inline T read() {
    T x = 0; bool flag = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') flag = 0; c = getchar();}
    while (isdigit(c)) {x = (x << 3) + (x << 1) + c - '0'; c = getchar();}
    if (flag) return x;
    return ~(x - 1);
}
template <typename T> inline void write(T x) {
    int stk[30], top = 0;
    if (x < 0) {putchar('-'); x = ~(x - 1);}
    while (x) stk[++top] = x % 10, x /= 10;
    if (!top) stk[++top] = 0;
    while (top) putchar(stk[top--] ^ 48);
    puts("");
    return ;
}
const int N = 1e5 + 5 + 10;
struct Num{
    int val, nw, f;
}a[N];
int opt[N], len, n, m, id[N], tot;
int L[N], R[N], t[N], s[320][N], f[320][320];
bool cmp1(Num x, Num y) {return x.val < y.val;}
bool cmp2(Num x, Num y) {return x.f < y.f;}
signed main() {
    n = read<int>(), m = read<int>();
    len = sqrt(n); //块长
    for (reg int i = 1; i <= n; ++i) {
        a[i].val = read<int>(); //原值
        a[i].f = i; //顺序
    }
    sort(a + 1, a + n + 1, cmp1); //从小到大排序
    a[0].nw = 0;
    for (reg int i = 1; i <= n; ++i) { //离散化
        a[i].nw = a[i - 1].nw; //继承上一个值的离散值
        if (a[i].val != a[i - 1].val) { //与上一个值不相等
            a[i].nw++; //离散值加一
            opt[++tot] = a[i].val; //原值存数组
        }
    }
    sort(a + 1, a + n + 1, cmp2); //用记录的顺序排序，回到初始位置
    for (reg int i = 1; i <= n; ++i) { //分块
        id[i] = (i - 1) / len + 1; //所属块
        if (id[i - 1] != id[i]) L[id[i]] = i; //左边界
        R[id[i]] = i; //右边界
        s[id[i]][a[i].nw]++; //每个值出现的次数
    }
    for (reg int i = 1; i <= id[n]; ++i)
        for (reg int j = 1; j <= tot; ++j)
            s[i][j] += s[i - 1][j]; //前缀和，前i块中j出现的次数
    for (reg int i = 1; i <= id[n]; ++i) //处理f数组，第i块~第j块 的众数
        for (reg int j = i; j <= id[n]; ++j) {
            int Minn_Mode = f[i][j - 1]; //继承 第i块~第j-1块 的众数
            int pre = s[j][Minn_Mode] - s[i - 1][Minn_Mode]; //求出出现次数
            for (reg int k = L[j]; k <= R[j]; ++k) { //因为加了一块，所以有特殊情况
                int now = s[j][a[k].nw] - s[i - 1][a[k].nw]; //算出这个数出现次数
                if ((now > pre) || (now == pre && a[k].nw < Minn_Mode)) //比较
                    Minn_Mode = a[k].nw, pre = now; //更新
            }
            f[i][j] = Minn_Mode; //最终答案
        }
    int x = 0;
    for (int i = 1; i <= m; ++i) {
        int l = read<int>(), r = read<int>();
        l = (l + x - 1) % n + 1, r = (r + x - 1) % n + 1;
        int ans = 0;
        if (l > r)
            swap(l, r);
        int st = id[l], ed = id[r]; //st为起始块，ed为末尾块
        if (ed - st <= 1) { //判断是否没有完整块
            for (int i = l; i <= r; ++i) //没有完整块，直接暴力
                t[a[i].nw]++;
            for (int i = l; i <= r; ++i)
                if (t[a[i].nw] > t[ans]|| (t[a[i].nw] == t[ans] && a[i].nw < ans))
                    ans = a[i].nw; //取出现次数最多并且小，更新
            for (int i = l; i <= r; ++i)
                t[a[i].nw] = 0; //清空桶
        }
        else { //有完整块
            //开头结尾都用暴力
            for (int i = l; i <= R[st]; ++i)
                t[a[i].nw]++;
            for (int i = L[ed]; i <= r; ++i)
                t[a[i].nw]++;
            ans = f[st + 1][ed - 1]; //取完整块里的众数
            int pre = s[ans][ed - 1] - s[ans][st] + t[ans]; //众数在[l, r]出现次数
            //这个众数只是中间块的，加上了开头结尾的不完整块可能有所改变
            for (int i = l; i <= R[st]; ++i) { //起始块对答案的影响
                //这个数在[l, r]间出现的次数
                int now = s[a[l].nw][ed - 1] - s[a[i].nw][st] + t[a[i].nw];
                //判断是否比当前更优 & 更新
                if (pre < now || (pre == now && a[i].nw < ans))
                    ans = a[i].nw, pre = now;
            }
            for (int i = L[ed]; i <= r; ++i) { //末尾块对于答案也有影响
                int now = s[a[i].nw][ed - 1] - s[a[i].nw][st] + t[a[i].nw];
                if (pre < now || (pre == now && a[i].nw < ans))
                    ans = a[i].nw, pre = now;
            }
            //清空桶
            for (int i = l; i <= R[st]; ++i)
                t[a[i].nw] = 0;
            for (int i = L[ed]; i <= r; ++i)
                t[a[i].nw] = 0;
        }
        x = opt[ans]; //离散值查原值
        write(x); //输出
    }
}

调一上午了，救救孩子吧