分块样例过对拍拍不出来全 WA 求调

RT

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a[100001], b[100001], tag[100001]; // a: 原数组 b: 离散化后的数组
ll n, m, sum, len;
ll f[500][500], s[500][50010];
ll buk[100001]; // 临时桶
// f(i, j): i ~ j 块中的众数
// s(i, j): j 在前 i 块中出现的次数

ll solve(ll l, ll r)
{
    ll ans = 0, lt = tag[l], rt = tag[r];
    if (tag[l] == tag[r])
    {
        for (int i = l; i <= r; i++) buk[b[i]]++;
        for (int i = l; i <= r; i++)
            if ((buk[b[i]] > buk[ans]) || (buk[b[i]] == buk[ans] && b[i] < ans)) ans = b[i];
        for (int i = l; i <= r; i++) buk[b[i]] = 0;
        return a[ans];
    }
    else
    {
        ans = f[lt + 1][rt - 1];
        for (int i = l; i <= min(n, lt * len); i++)
            buk[b[i]]++;
        for (int i = (rt - 1) * len + 1; i <= r; i++)
            buk[b[i]]++;

        for (int i = l; i <= min(n, lt * len); i++)
        {
            int now = buk[b[i]] + s[rt - 1][b[i]] - s[lt][b[i]],
            org = buk[ans] + s[rt - 1][ans] - s[lt][ans];
            if ((now > org) || ((now == org) && b[i] < ans))
                ans = b[i];
        }
        for (int i = (rt - 1) * len + 1; i <= r; i++)
        {
            int now = buk[b[i]] + s[rt - 1][b[i]] - s[lt][b[i]],
            org = buk[ans] + s[rt - 1][ans] - s[lt][ans];
            if ((now > org) || ((now == org) && b[i] < ans))
                ans = b[i];
        }

        for (int i = l; i <= min(n, lt * len); i++)
            buk[b[i]] = 0;
        for (int i = (rt - 1) * len + 1; i <= r; i++)
            buk[b[i]] = 0;
        return a[ans];
    }
}

int main()
{
    cin >> n >> m;
    len = int(sqrt(n));
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i], tag[i] = (i - 1) / len + 1;
    sort(a + 1, a + n + 1);
    sum = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; i++)
        b[i] = lower_bound(a + 1, a + 1 + sum, b[i]) - a;
    for (int i = 1; i <= tag[n]; i++)
    {
        for (int j = (i - 1) * len + 1; j <= min(n, len * i); j++)
            s[i][b[j]]++;
        for (int j = 1; j <= sum; j++)
            s[i][j] += s[i - 1][j];
    }

    for (int i = 1; i <= tag[n]; i++)
        for (int j = i; j <= tag[n]; j++)
        {
            int maxx = f[i][j - 1];
            for (int k = (j - 1) * len + 1; k <= min(len * j, n); k++)
                if ( (s[j][b[k]] - s[i - 1][b[k]] > s[j][maxx] - s[i - 1][maxx])
                    || ( (s[j][b[k]] - s[i - 1][b[k]] == s[j][maxx] - s[i - 1][maxx]) && b[k] < maxx) )
                    maxx = b[k];
            f[i][j] = maxx;
        }

    ll l, r, x = 0;
    while (m--)
    {
        ll l0, r0;
        cin >> l0 >> r0;
        l = ((l0 + x - 1) % n) + 1, r = ((r0 + x - 1) % n) + 1;
        if (l > r) swap(l, r);
        x = solve(l, r);
        cout << x << endl;
    }
    return 0;
}