题面：[Violet] 蒲公英

题目背景

亲爱的哥哥：

你在那个城市里面过得好吗？

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！

哥哥你要快点回来哦！

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

题目描述

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

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

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

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

输入格式

第一行有两个整数，分别表示蒲公英的数量 $n$ 和询问次数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 棵蒲公英的种类 $a_i$。

接下来 $m$ 行，每行两个整数 $l_0, r_0$，表示一次询问。输入是加密的，解密方法如下：

令上次询问的结果为 $x$（如果这是第一次询问，则 $x = 0$），设 $l=((l_0+x-1)\bmod n) + 1,r=((r_0+x-1) \bmod n) + 1$。如果 $l > r$，则交换 $l, r$。
最终的询问区间为计算后的 $[l, r]$。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5

样例输出 #1

1
2
3
1 
2 
1

提示

数据规模与约定

  • 对于 $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$。

简化题意

区间查询众数，强制在线（很简短食不食

思路：$O(n\sqrt{n}\log n)$

这里提供一个新颖的做法，相比于某谷里的题解，我们的复杂度多了一个 log 这也使得题目的思维难度大大滴降低。

我们首先考虑分块后如何处理。对于整块，我们可以直接大力预处理所有整块之间的众数。意思就是说，查询被分为了整块和小块，而众数一定是小块中的一个数，以及若干整块的众数。比如说我们有 $1\sim \left\lfloor\sqrt n\right\rfloor$ （ 后记 $BN = \left\lfloor\sqrt n\right\rfloor$ ）这些整块，我们直接大力与处理出 $[1,1],[1,2],\dots,[2,2],[2,3],\dots,[BN,BN]$ 这些整块之间的众数，复杂度大概就是 $O(n\sqrt n)$ 。

那么对于小块，我们直接大力处理出每一种数字出现的位置，直接二分查找小块里的数字在查询区间中出现了多少次，这样就可以以 $O(n\sqrt{n}\log 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 40010;

int n, Q;
int a[N];

int c[N];
vector<int >idx[N];

int cnt[N];
int ds[1010][1010], B;

inline void Input() {
    read(n, Q);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
}

inline void Init() {
    for(int i = 1; i <= n; i++) c[i] = a[i];
    sort(c + 1, c + n + 1); 
    int m = unique(c + 1, c + n + 1) - c;
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(c + 1, c + m, a[i]) - c;
        idx[a[i]].push_back(i);
    }
    B = sqrt(n);
    for(int l = 0; l <= n; l += B) {
        if(l == 0) continue;
        for(int i = 1; i <= m; i++) cnt[i] = 0;
        int ans = 0;
        for(int r = l; r <= n; r++) {
            cnt[a[r]]++;
            if(cnt[a[r]] > cnt[ans] || cnt[a[r]] == cnt[ans] && a[r] < ans) ans = a[r];
            if((r + 1) % B == 0 || r == n) ds[l / B][r / B] = ans;
        }
    }
}

inline int Calc(int l, int r, int x) {
    return upper_bound(idx[x].begin(), idx[x].end(), r) - lower_bound(idx[x].begin(), idx[x].end(), l);
}

inline int Query(int l, int r) {
    int idl = l / B, idr = r / B;
    int ans = 0;
    if(idl -1 < idr) ans = ds[idl + 1][idr - 1];
    int lst = Calc(l, r, ans), now = 0;
    if(idl == idr) {
        for(int i = l; i <= r; i++) {
            now = Calc(l, r, a[i]);
            if(lst < now || lst == now && a[i] < ans) {
                ans = a[i], lst = now;
            }
        }
        return c[ans];
    }
    for(int i = l; i < (idl + 1) * B; i++) {
        now = Calc(l, r, a[i]);
        if(lst < now || now == lst && a[i] < ans) {
            ans = a[i], lst = now;
        }
    }
    for(int i = idr * B; i <= r; i++) {
        now = Calc(l, r, a[i]);
        if(lst < now || now == lst && a[i] < ans) {
            ans = a[i], lst = now;
        }
    }
    return c[ans];
}

inline void Work() {
    Init();
    int ans = 0, l, r;
    while(Q--) {
        scanf("%d%d", &l, &r);
        l = (l + ans - 1) % n + 1;
        r = (r + ans - 1) % n + 1;
        if(l > r) swap(l, r);
        ans = Query(l, r);
        printf("%d\n", ans);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}