刚学OI一秒钟的萌新求助分块

离散化+预处理+分块，同题解做法

查出了无数个小错，可能是L，R的判定有锅

#include<bits/stdc++.h>
using namespace std;
int n, m, a[50005], b[50005], ans[305][305], cnt[50005][305], ll[305], rr[305], sum[50005], size;
int getL(int x)
{
    if(x % size == 0)
    {
        return x / size + 1;
    }
    else if(x % size == 1)
    {
        return x / size + 1;
    }
    return x / size + 2;
}
void init()
{
    ll[1] = 1;
    int tot = 1;
    size = sqrt(n);
    for(int i = 1; i <= n; i++)
    {
        if(i % size == 0)
        {
            rr[tot] = i;
            ll[++tot] = i + 1;
        }
    }
    rr[tot] = n;
    ll[tot + 1] = n + 1;
    rr[tot + 1] = n + 1;
    for(int i = 1; i <= tot; i++)
    {
        int st = ll[i], maxv = -0x3f3f3f3f, k = 0x3f3f3f3f;
        memset(sum, 0, sizeof(sum));
        for(int j = i; j <= tot; j++)
        {
            int ed = rr[j];
            while(st <= ed)
            {
                int v = ++sum[a[st]];
                if(v > maxv)
                {
                    maxv = v;
                    k = a[st];
                }
                else if(v == maxv && a[st] < k)
                {
                    k = a[st];
                }
                st++;
            }
            ans[i][j] = k;
        }
    }
    memset(sum, 0, sizeof(sum));
    for(int i = 1; i <= tot; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cnt[a[j]][i] = cnt[a[j]][i - 1];
        }
        for(int j = ll[i]; j <= rr[i]; j++)
        {
            cnt[a[j]][i] = ++sum[a[j]];
        }
    }
    return;
}
int query(int l, int r)
{
    int maxv = -0x3f3f3f3f, k = 0x3f3f3f3f;
    memset(sum, 0, sizeof(sum));
    if(r - l < 2 * size)
    {
        for(int i = l; i <= r; i++)
        {
            int v = ++sum[a[i]];
            if(v > maxv)
            {
                maxv = v;
                k = a[i];
            }
            else if(v == maxv && a[i] < k)
            {
                k = a[i];
            }
        }
        return b[k];
    }
    int L = getL(l), R = r / size;
    k = ans[L][R];
    maxv = cnt[k][R] - cnt[k][L - 1];
    //cout << maxv << " " << R << " " << L-1 << endl;
    int st = rr[R], ed = ll[L];
    for(int i = l; i < ed; i++)
    {
        int v = ++sum[a[i]] + cnt[a[i]][R] - cnt[a[i]][L - 1];
        if(v > maxv)
        {
            maxv = v;
            k = a[i];
        }
        else if(v == maxv && a[i] < k)
        {
            k = a[i];
        }
    }
    for(int i = st + 1; i <= r; i++)
    {
        int v = ++sum[a[i]] + cnt[a[i]][R] - cnt[a[i]][L - 1];
        if(v > maxv)
        {
            maxv = v;
            k = a[i];
        }
        else if(v == maxv && a[i] < k)
        {
            k = a[i];
        }
    }
    return b[k];
}
int main()
{
    //freopen("P4168_1.in", "r", stdin);
    //freopen("P4168_1.ans", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int ss = unique(b + 1, b + n + 1) - b;
    for(int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(b + 1, b + ss + 1, a[i]) - b;
    }
    init();
    int l, r, last = 0;
    for(int i = 1; i <= m; i++)
    {
        cin >> l >> r;
        l = (l + last - 1) % n + 1;
        r = (r + last - 1) % n + 1;
        if(l > r)
        {
            swap(l, r);
        }
        last = query(l, r);
        cout << last << endl;
    }
    return 0;
}