跳转至

分块

静态区间众数查询

P4168 [Violet] 蒲公英

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为 \(n\) 的序列 \(\{a_1,a_2..a_n\}\)，其中 \(a_i\) 为一个正整数，表示第 \(i\) 棵蒲公英的种类编号。

而每次询问一个区间 \([l, r]\)，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

  • 对于 \(20\%\) 的数据，保证 \(n,m \le 3000\)。
  • 对于 \(100\%\) 的数据，保证 \(1\le n \le 40000\)， \(1\le m \le 50000\)， \(1\le a_i \le 10^9\)， \(1 \leq l_0, r_0 \leq n\)。
实现 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
#define N 40005
#define M 205
int n, m, q, a[N], tot, to[N], sz[M][N], md[M][M], l[M], r[M], id[N], all[N];
pair<int, int> p[N];
void init()
{
    m = sqrt(n);
    for (int i = 1; i <= m; i++)
    {
        l[i] = r[i - 1] + 1;
        r[i] = l[i] + m - 1;
    }
    if (r[m] < n)
    {
        m++;
        l[m] = r[m - 1] + 1;
        r[m] = n;
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= tot; j++)
            sz[i][j] = sz[i - 1][j];
        for (int j = l[i]; j <= r[i]; j++)
        {
            id[j] = i;
            sz[i][a[j]]++;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = i; j <= m; j++)
        {
            md[i][j] = md[i][j - 1];
            for (int k = l[j]; k <= r[j]; k++)
            {
                all[a[k]]++;
                if (all[a[k]] > all[md[i][j]] || (all[a[k]] == all[md[i][j]] && a[k] < md[i][j]))
                    md[i][j] = a[k];
            }
        }
        memset(all, 0, sizeof(all));
    }
}
int query(int x, int y)
{
    int ans = 0;
    if (id[y] - id[x] <= 1)
    {
        for (int i = x; i <= y; i++)
        {
            all[a[i]]++;
            if (all[a[i]] > all[ans] || (all[a[i]] == all[ans] && a[i] < ans))
                ans = a[i];
        }
        for (int i = x; i <= y; i++)
            all[a[i]]--;
        return ans;
    }
    int u = id[x];
    int v = id[y];
    ans = md[u + 1][v - 1];
    for (int i = x; i <= r[u]; i++)
    {
        sz[v - 1][a[i]]++;
        if (sz[v - 1][a[i]] - sz[u][a[i]] > sz[v - 1][ans] - sz[u][ans] || (sz[v - 1][a[i]] - sz[u][a[i]] == sz[v - 1][ans] - sz[u][ans] && a[i] < ans))
            ans = a[i];
    }
    for (int i = l[v]; i <= y; i++)
    {
        sz[v - 1][a[i]]++;
        if (sz[v - 1][a[i]] - sz[u][a[i]] > sz[v - 1][ans] - sz[u][ans] || (sz[v - 1][a[i]] - sz[u][a[i]] == sz[v - 1][ans] - sz[u][ans] && a[i] < ans))
            ans = a[i];
    }
    for (int i = x; i <= r[u]; i++)
        sz[v - 1][a[i]]--;
    for (int i = l[v]; i <= y; i++)
        sz[v - 1][a[i]]--;
    return ans;
}
int main(void)
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        p[i] = {a[i], i};
    }
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        if (p[i].first != p[i - 1].first)
            to[++tot] = p[i].first;
        a[p[i].second] = tot;
    }
    init();
    int last = 0;
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x = (x + last - 1) % n + 1;
        y = (y + last - 1) % n + 1;
        if (x > y)
            swap(x, y);
        last = to[query(x, y)];
        printf("%d\n", last);
    }
    return 0;
}