10 pts 求调，悬五关

Stone_Xz @ 2024-10-10 20:08:29

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

const int N = 4e4 + 5, K = 2e2 + 5;

int n, m, a[N], b[N], cnt, ans;

int tot = 1, klen, s[K][N], z[K][K], kuai[N];

void lisanhua()
{
    sort(b + 1, b + 1 + n);
    cnt = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
}

void get_s()
{
    for(int i = 1; i <= tot; i++)
        for(int j = 1; j <= min(klen * i, n); j++)
            s[i][a[j]] ++;
}

void get_z()
{
    for(int i = 1; i <= tot; i++)
    for(int j = i; j <= tot; j++)
    {
        int res = z[i][j - 1];
        int maxi = s[j - 1][res] - s[i - 1][res];
        for(int k = (j - 1) * klen + 1; k <= min(klen * j, n); k++)
        {
            int ci = s[j][a[k]] - s[i - 1][a[k]];
            if(ci > maxi || (ci == maxi && a[k] < res)) {
                res = a[k];
                maxi = ci;
            }
        }
        z[i][j] = res;
    }
}

int query(int lt, int rt)
{
    int tmp[N], maxi = 0, res = 0;
    fill(tmp + 1, tmp + 1 + n, 0);
    for(int i = lt; i <= min(klen * kuai[lt], rt); i++)
    {
        tmp[a[i]] ++;
        if(tmp[a[i]] > maxi || (tmp[a[i]] == maxi && a[i] < res)) {
            maxi = tmp[a[i]];
            res = a[i];
        }
    }
    if(kuai[lt] == kuai[rt])
        return res;
    for(int i = max(lt, (kuai[rt] - 1) * klen + 1); i <= rt; i++)
    {
        tmp[a[i]] ++;
        if(tmp[a[i]] > maxi || (tmp[a[i]] == maxi && a[i] < res)) {
            maxi = tmp[a[i]];
            res = a[i];
        }
    }
    if(kuai[rt] == kuai[lt] + 1)
        return res;
    int L = kuai[lt], R = kuai[rt];
    res = z[L][R];
    maxi = s[R - 1][res] - s[L][res];
    for(int i = lt; i <= min(klen * kuai[lt], n); i++)
    {
        int ci = s[R - 1][a[i]] - s[L][a[i]] + tmp[a[i]];
        if(ci > maxi || (ci == maxi && a[i] < res)) {
            maxi = ci;
            res = a[i];
        }
    }
    for(int i = (kuai[rt] - 1) * klen + 1; i <= rt; i++)
    {
        int ci = s[R - 1][a[i]] - s[L][a[i]] + tmp[a[i]];
        if(ci > maxi || (ci == maxi && a[i] < res)) {
            maxi = ci;
            res = a[i];
        }
    }
    return res;
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    klen = sqrt(n);
    for(int i = 1, tmp = 0; i <= n; i++)
    {
        cin >> a[i]; b[i] = a[i];
        kuai[i] = tot;
        if(++tmp == klen && i != n) {
            tmp = 0;
            tot++;
        }
    }
    lisanhua();
    get_s(); // 求前 i 个块有几个排名为 j 的数 
    get_z(); // 求块 i 到 块 j 的众数 
    while(m--)
    {
        int l, r; cin >> l >> r;
        l = ((l + ans - 1) % n) + 1;
        r = ((r + ans - 1) % n) + 1;
        if(l > r) swap(l, r);
//      cout << "[l, r] = " << l << " " << r << "\n";
        ans = b[query(l, r)];
        cout << ans << "\n";
    }
    return 0;
}
// By Stone_XUANzhe
// 周！防！有！希！ 

by Super_Cube @ 2024-10-10 20:18:56

@shixuanzhe_ha

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

const int N = 4e4 + 5, K = 2e2 + 5;

int n, m, a[N], b[N], cnt, ans;

int tot = 1, klen, s[K][N], z[K][K], kuai[N];

void lisanhua()
{
    sort(b + 1, b + 1 + n);
    cnt = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
}

void get_s()
{
    for(int i = 1; i <= tot; i++)
        for(int j = 1; j <= min(klen * i, n); j++)
            s[i][a[j]] ++;
}

void get_z()
{
    for(int i = 1; i <= tot; i++)
    for(int j = i; j <= tot; j++)
    {
        int res = z[i][j - 1];
        int maxi = s[j - 1][res] - s[i - 1][res];
        for(int k = (j - 1) * klen + 1; k <= min(klen * j, n); k++)
        {
            int ci = s[j][a[k]] - s[i - 1][a[k]];
            if(ci > maxi || (ci == maxi && a[k] < res)) {
                res = a[k];
                maxi = ci;
            }
        }
        z[i][j] = res;
    }
}

int query(int lt, int rt)
{
    int tmp[N], maxi = 0, res = 0;
    fill(tmp + 1, tmp + 1 + n, 0);
    for(int i = lt; i <= min(klen * kuai[lt], rt); i++)
    {
        tmp[a[i]] ++;
        if(tmp[a[i]] > maxi || (tmp[a[i]] == maxi && a[i] < res)) {
            maxi = tmp[a[i]];
            res = a[i];
        }
    }
    if(kuai[lt] == kuai[rt])
        return res;
    for(int i = max(lt, (kuai[rt] - 1) * klen + 1); i <= rt; i++)
    {
        tmp[a[i]] ++;
        if(tmp[a[i]] > maxi || (tmp[a[i]] == maxi && a[i] < res)) {
            maxi = tmp[a[i]];
            res = a[i];
        }
    }
    if(kuai[rt] == kuai[lt] + 1)
        return res;
    int L = kuai[lt], R = kuai[rt];
    res = z[L+1][R-1];
    maxi = s[R - 1][res] - s[L][res];
    for(int i = lt; i <= min(klen * kuai[lt], n); i++)
    {
        int ci = s[R - 1][a[i]] - s[L][a[i]] + tmp[a[i]];
        if(ci > maxi || (ci == maxi && a[i] < res)) {
            maxi = ci;
            res = a[i];
        }
    }
    for(int i = (kuai[rt] - 1) * klen + 1; i <= rt; i++)
    {
        int ci = s[R - 1][a[i]] - s[L][a[i]] + tmp[a[i]];
        if(ci > maxi || (ci == maxi && a[i] < res)) {
            maxi = ci;
            res = a[i];
        }
    }
    return res;
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    klen = sqrt(n);
    for(int i = 1, tmp = 0; i <= n; i++)
    {
        cin >> a[i]; b[i] = a[i];
        kuai[i] = tot;
        if(++tmp == klen && i != n) {
            tmp = 0;
            tot++;
        }
    }
    lisanhua();
    get_s(); // 求前 i 个块有几个排名为 j 的数 
    get_z(); // 求块 i 到 块 j 的众数 
    while(m--)
    {
        int l, r; cin >> l >> r;
        l = ((l + ans - 1) % n) + 1;
        r = ((r + ans - 1) % n) + 1;
        if(l > r) swap(l, r);
//      cout << "[l, r] = " << l << " " << r << "\n";
        ans = b[query(l, r)];
        cout << ans << "\n";
    }
    return 0;
}
// By Stone_XUANzhe
// 周！防！有！希！ 

by Stone_Xz @ 2024-10-10 20:27:29

%%%%%%%%%%%%%%% @Super_Cube orz

thx！

by Stone_Xz @ 2024-10-10 20:31:53

@Super_Cube 五关已给，此贴结