题目描述

样例

blablabla

算法1

$O(nt + m *n * log n / t)$

就是书上的方法二，先离散化+预处理 O(nt + nlongn), t为总共的分块数, len为块的大小
当 r - l + 1 >= len * 2 - 1, 则l-r内必有一个整块(包含边界)
1.如果不想麻烦，可以对 r - l + 1 < len * 2 - 1 直接暴力，从 l 到到r，按书上二分方法去查找在l-r直接a[i]的个数，暴力找答案
2.l为块左边界 （l % len == 1）,r为右边界（r % len == 0 || r == n(最后不足一块)）,预处理已经知道答案
3.l为块左边界，找到r 所在块的左边界 rl，预处理知道答案 l-（lr - 1）， 暴力rl - r
3.r为块右边界， 同上
4.分别找 rl 和 lr，预处理知道 (lr + 1) - (rl - 1)的答案，暴力l - rl、 rl - r即可

大概复杂度为 O(nt + m *n * log n / t), 求导 t = （m * n * log(n)）^ (1/3), 所以我的分块比 piiiiig 大佬的快一点， 不过因为t较大，前后缀和是不太可能

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
#define find(x) ((x - 1) / len + 1)
#define wide(l,r) (r - l + 1)
using namespace std;

const int maxn = 4e4 + 5;
const int maxt = 3130;

int len, t, n, m, a[maxn], b[maxn], f[maxt][maxt], tax[maxn], x;
vector<int> ve[maxn];

void init()
{
    t = (int)sqrt(n * log2(n));
    len = (n - 1) / t + 1;
    sort(b + 1, b + 1 + n);
    int tot = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++ i)
    {
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
        ve[a[i]].push_back(i);
    }
    for (int i = 1; i <= t; ++ i, memset(tax, 0, sizeof tax))
    {
        int mid = (i - 1) * len + 1;
        for (int j = (i - 1) * len + 1; j <= n; ++ j)
        {
            ++ tax[a[j]];
            if (mid != a[j])
            {
                if (tax[mid] < tax[a[j]]) mid = a[j];
                else if (tax[mid] == tax[a[j]] && mid > a[j]) mid = a[j];
            }
            if (j % len == 0 || j == n) f[i][find(j)] = mid;
        }
    }
}

int get(int l, int r, int k)
{
    int ll = lower_bound(ve[k].begin(), ve[k].end(), l) - ve[k].begin();
    if (ll == ve[k].size()) return 0;
    return upper_bound(ve[k].begin(), ve[k].end(), r) - ve[k].begin() - ll;
}

int work(int cnt, int l, int r, int ll, int rr)
{
    for (int j = l, res; j <= r; ++ j)
    {
        if (x != a[j] || j == l)
        {
            res = get(ll, rr, a[j]);
            if (cnt < res) cnt = res, x = a[j];
            else if (cnt == res && x > a[j]) x = a[j];
        }
    }
    return cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", a + i), b[i] = a[i];
    init();
    for (int i = 1, l, r; i <= m; ++ i)
    {
        scanf("%d%d", &l, &r);
        l = (b[x] % n - 1 + l) % n + 1, r = (b[x] % n - 1 + r) % n + 1;
        if (l > r) swap(l, r);
        if (wide(l, r) < len << 1) work(0, l, r, l, r);
        else if (l % len == 1 && (r % len == 0 || r == n)) x = f[find(l)][find(r)];
        else if (l % len == 1)
        {
            int rl = (find(r) - 1) * len + 1;
            x = f[find(l)][find(r) - 1];
            work(get(l, r, x), rl, r, l, r);
        }
        else if (r % len == 0)
        {
            int lr = find(l) * len;
            x = f[find(l) + 1][find(r)];
            work(get(l, r, x), l, lr, l, r);
        }
        else
        {
            int lr = find(l) * len, rl = (find(r) - 1) * len + 1;
            x = f[find(l) + 1][find(r) - 1];
            work(work(get(l, r, x), l, lr, l, r), rl, r, l, r);
        }
        printf("%d\n", b[x]);
    }
    return 0;
}