题目描述

传送门： 蒲公英

算法1

(分块+二分) $O(n \sqrt{mlog_n})$

我们可以按照书上的做法预处理出第$i$块到第$j$块的众数，用$d_{ij}$表示。然后建立一个$vector$存储每个数出现的位置，有了这个$vector$,我们就可以二分查找出一个数$val$在区间$l$到$r$内出现的次数。询问的时候对于中间的几块，我们直接拿已经预处理出的众数，然后旁边两个小块暴力查找，更新答案。
设我们分了$T$块,每块长度即为$n/T$,则预处理的时间复杂度为$O(nT)$,询问的时间复杂度为$O(m * n/T * log_n)$
由均值不等式可得，当$nT=m * n/T* log_n$时，复杂度最低，此时$T= \sqrt{mlog_n}$,所以块的大小就是 $n/ \sqrt{mlog_n}$
块的大小很重要，我在这TLE了好久，这个最终跑了21s

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include<cmath>
#include<functional>
using namespace std;
const int N = 1e5 + 10;
int n, m, block;
int a[N], b[N], f[N], tot;
int d[1000][1000];
vector<int> g[N];
int ct[N];
void build()
{
    block=max(1,(int)(n/sqrt(m*log2(n))));
    for (int i = 1; i <= n; i++)
        b[i] = (i - 1) / block + 1;
}
int Count(int l, int r, int val)
{
    int t = upper_bound(g[val].begin(), g[val].end(), r)- lower_bound(g[val].begin(), g[val].end(), l);
    return t;
}
void pre(int x)//预处理从块x到其他块的众数
{
    memset(ct, 0, sizeof(ct));
    int mx = -1, ans = 0;
    for (int i = (x - 1)*block + 1; i <= n; i++)
    {
        ct[a[i]]++;
        if (ct[a[i]] > mx || (ct[a[i]] == mx&&a[i] < ans))
        {
            ans = a[i];
            mx = ct[a[i]];
        }
        d[x][b[i]] = ans;
    }
}
int query(int l, int r)
{
    int ans = d[b[l] + 1][b[r] - 1];
    int mx = Count(l, r, ans);
    int cnt = 0;
    int up = min(r, b[l] * block);
    for (int i = l; i <= up; i++)
    {
        cnt = Count(l, r, a[i]);
        if (cnt > mx || (cnt == mx&&f[ans] > f[a[i]]))
        {
            mx = cnt;
            ans = a[i];
        }
    }
    if (b[l] != b[r])
    {
        for (int i = (b[r] - 1)*block + 1; i <= r; i++)
        {
            cnt =Count(l, r, a[i]);
            if (cnt > mx || (cnt == mx&&ans > a[i]))
            {
                mx = cnt;
                ans = a[i];
            }
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        f[i] = a[i];
    }
    build();
    sort(f + 1, f + n + 1);
    int N = unique(f + 1, f + n + 1) - f-1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(f + 1, f + N + 1, a[i]) - f;
        g[a[i]].push_back(i);
    }
    int ans = 0;
    for (int i = 1; i <= b[n]; i++)
        pre(i);
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + ans - 1) % n + 1;
        r = (r + ans - 1) % n + 1;
        if (l>r) swap(l, r);
        ans = f[query(l, r)];
        printf("%d\n", ans);
    }
    return 0;
}

算法2

(分块+后缀和) $O(n\sqrt{n})$

这个优化的地方在于每次省去了二分查找，直接用后缀和代替，在我们预处理的时候，$g_{ij}$表示第$i$块到$n$的区间内$j$出现的次数，这样就是后缀和，这样每次查找个数直接后缀和相减就好。整体复杂度为$O(n\sqrt{n})$,此时块的大小取$\sqrt{n}$即可。
这个代码跑了4秒，感觉优化还是挺大的,不过如果使用memset时间还是挺长的

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include<cmath>
#include<functional>
using namespace std;
const int N = 1e5 + 10;
const int T = 500;
int n, m, block;
int a[N], b[N], f[N], tot;
int d[1000][1000];
int g[T][N];
int ct[N];
int num[N],tmp[N];
void build()
{
    block = (int)sqrt(1.0*n);
    for (int i = 1; i <= n; i++)
        b[i] = (i - 1) / block + 1;
}
void pre(int x)//预处理
{
    int top = 0;
    int mx = -1, ans = 0;
    for (int i = (x - 1)*block + 1; i <= n; i++)
    {
        g[x][a[i]]++;
        ct[a[i]]++;
        if (ct[a[i]] == 1){
            tmp[++top] = a[i];//这里我是想省去memset的时间
        }
        if (ct[a[i]] > mx || (ct[a[i]] == mx&&a[i] < ans))
        {
            ans = a[i];
            mx = ct[a[i]];
        }
        d[x][b[i]] = ans;
    }
    while (top)
    {
        ct[tmp[top--]] = 0;;//这里我是想省去memset的时间
    }
}
int query(int l, int r)
{
    int p = b[l], q = b[r];
    int ans = 0, cnt = 0, top = 0;
    int up =  b[l] * block;
    if (q - p < 2)
    {
        for (int i = l; i<= r; i++)
        {
            ++ct[a[i]];
            if (ct[a[i]] == 1){
                tmp[++top] = a[i];
            }
        }
        while (top)
        {
            int x = tmp[top--];
            if (cnt < ct[x] || (cnt == ct[x] && x < ans))
            {
                ans = x;
                cnt = ct[x];
            }
            ct[x] = 0;
        }
        return ans;
    }
    for (int i = l; i <= up; i++)
    {
        ++ct[a[i]];
        if (ct[a[i]] == 1)
        {
            tmp[++top] = a[i];
            num[a[i]] = g[p + 1][a[i]] - g[q][a[i]];
        }
    }
    for (int i = (b[r] - 1)*block + 1; i <= r; i++)
    {
        ++ct[a[i]];
        if (ct[a[i]] == 1){
            tmp[++top] = a[i];
            num[a[i]] = g[p + 1][a[i]] - g[q][a[i]];
        }
    }
    ans = d[b[l] + 1][b[r] - 1];
    num[ans]=g[p + 1][ans] - g[q][ans];//这个一定别忘了，因为ans可能未在旁边两块出现过。
    cnt = ct[ans]+num[ans];
    while (top)
    {
        int x = tmp[top--];
        ct[x] += num[x];
        if (cnt < ct[x] || (cnt == ct[x] && x < ans))
        {
            ans = x;
            cnt = ct[x];
        }
        ct[x] = 0;
        num[x]=0;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        f[i] = a[i];
    }
    build();
    sort(f + 1, f + n + 1);
    int N = unique(f + 1, f + n + 1) - f - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(f + 1, f + N + 1, a[i]) - f;
    }
    int ans = 0;
    for (int i = 1; i <= b[n]; i++)
        pre(i);
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + ans - 1) % n + 1;
        r = (r + ans - 1) % n + 1;
        if (l>r) swap(l, r);
        ans = f[query(l, r)];
        printf("%d\n", ans);
    }
    return 0;
}