$ \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<bits/stdc++.h>

#define LL long long

LL 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;

}