$ \color{#0066ff}{ 题目描述 }$
在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为n的序列 \((a_1,a_2..a_n)\)，其中 \(a_i\) 为一个正整数，表示第i棵蒲公英的种类编号。
而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。
注意，你的算法必须是在线的
\(\color{#0066ff}{输入格式}\)
第一行两个整数 n,m ，表示有n株蒲公英，m 次询问。
接下来一行n个空格分隔的整数 \(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]。
\(\color{#0066ff}{输出格式}\)
输出m 行。每行一个整数，表示每次询问的结果。
\(\color{#0066ff}{输入样例}\)
6 3 1 2 3 2 1 2 1 5 3 6 1 5
\(\color{#0066ff}{输出样例}\)
1 2 1
\(\color{#0066ff}{数据范围与提示}\)
对于 20% 的数据，保证 \(1\le n,m \le 3000\)
对于 100% 的数据，保证 \(1\le n \le 40000,1\le m \le 50000,1\le a_i \le 10^9\)
\(\color{#0066ff}{题解}\)
一看这数据范围，当然是分块啦
我们考虑询问，如果在一个块内，显然可以直接\(O(\sqrt n)\)扫一遍出结果
如果不在一个块内呢？ 我们考虑哪些位置上的数可能成为答案
无非就是l和r所在的残块的值还有中间所有整块的值
总共最多有\(2*\sqrt n+1\)个
我们可以预处理一个数组\(p[i][j]\)为第i块到第j块的众数，就行了
然后对于残块的值，我们还要知道在整块中出现了多少次，于是记一个前缀和\(s[i][j]\)在前i块中j出现了多少次，这样就能快速解决了
a比较大，要离散化一下
// luogu-judger-enable-o2#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}const int inf = 0x7fffffff;const int maxn = 4e5 + 10;int a[maxn], b[maxn], bel[maxn], sqt;int s[202][maxn], ls[maxn], p[250][250];struct node { int l, r, len; node() { l = inf; r = len = 0; }}e[250];int n, m;int query(int l, int r) { int maxnum = 0, maxstep = 0; if(bel[l] == bel[r]) { for(int i = l; i <= r; i++) { ls[a[i]]++; if((ls[a[i]] > maxstep) || (ls[a[i]] == maxstep && a[i] < maxnum)) maxnum = a[i], maxstep = ls[a[i]]; } for(int i = l; i <= r; i++) ls[a[i]]--; return maxnum; } else { for(int i = l; i <= e[bel[l]].r; i++) { ls[a[i]]++; int num = ls[a[i]] + s[bel[r] - 1][a[i]] - s[bel[l]][a[i]]; if((num > maxstep) || (num == maxstep && a[i] < maxnum)) maxnum = a[i], maxstep = num; } for(int i = e[bel[r]].l; i <= r; i++) { ls[a[i]]++; int num = ls[a[i]] + s[bel[r] - 1][a[i]] - s[bel[l]][a[i]]; if((num > maxstep) || (num == maxstep && a[i] < maxnum)) maxnum = a[i], maxstep = num; } if(bel[l] + 1 != bel[r]) { int now = p[bel[l] + 1][bel[r] - 1]; int num = ls[now] + s[bel[r] - 1][now] - s[bel[l]][now]; if((num > maxstep) || (num == maxstep && now < maxnum)) maxnum = now, maxstep = num; } for(int i = l; i <= e[bel[l]].r; i++) ls[a[i]]--; for(int i = e[bel[r]].l; i <= r; i++) ls[a[i]]--; return maxnum; }}int main() { n = in(), m = in(); for(int i = 1; i <= n; i++) a[i] = b[i] = in(); std::sort(b + 1, b + n + 1); int num = 1; for(int i = 2; i <= n; i++) if(b[i] ^ b[i - 1]) b[++num] = b[i]; for(int i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + num + 1, a[i]) - b; sqt = sqrt(n); for(int i = 1; i <= n; i++) { int &now = bel[i]; now = (i - 1) / sqt + 1; e[now].l = std::min(e[now].l, i); e[now].r = std::max(e[now].r, i); s[now][a[i]]++; } for(int i = 1; i <= bel[n]; i++) for(int j = 1; j <= num; j++) s[i][j] += s[i - 1][j]; for(int i = 1; i <= bel[n]; i++) { for(int j = 1; j <= num; j++) ls[j] = 0; int maxnum = 0, maxstep = 0; for(int j = i; j <= bel[n]; j++) { for(int k = e[j].l; k <= e[j].r; k++) { ls[a[k]]++; if((ls[a[k]] > maxstep) || (ls[a[k]] == maxstep && a[k] < maxnum)) maxstep = ls[a[k]], maxnum = a[k]; } p[i][j] = maxnum; } } for(int i = 1; i <= num; i++) ls[i] = 0; LL ans = 0; while(m --> 0) { LL l = (in() + ans - 1) % n + 1; LL r = (in() + ans - 1) % n + 1; if(l > r) std::swap(l, r); printf("%lld\n", ans = b[query(l, r)]); } return 0;}