0pts.TAT

照李煜东方法二写的.

义父, 帮调下吧

#include<bits/stdc++.h>
#define int long long
#define N 40001
#define M 50001
#define T 2700
using namespace std;
struct data{int n, c; } maj[T][T];
int n, m, a[N], h[N], bel[N], d, t, Max, cnt[N], ans;
vector<int> v[M];
int L(int x) {return (x-1)*d+1; }
int R(int x) {return min(n, x*d); }
void init() {
	for (int i=1; i<=n; ++i) h[i]=a[i];
	sort(h+1, h+n+1);
	Max=unique(h+1, h+n+1)-h-1;
	for (int i=1; i<=n; ++i)
		a[i]=lower_bound(h+1, h+Max+1, a[i])-h;
	for (int i=1; i<=n; ++i)
		v[a[i]].push_back(i);
	d=sqrt(n*log2(n)), t=(n+d-1)/d;
	for (int i=1; i<=d; ++i)
		for (int j=L(i); j<=R(i); ++j)
			bel[j]=i;
	for (int i=1; i<=t; ++i)
		for (int j=i; j<=t; ++j) {
			for (int k=1; k<=Max; ++k)
				cnt[k]=0;
			for (int k=L(i); k<=R(j); ++k)
				++cnt[a[k]];
			for (int k=1; k<=Max; ++k)
				if (cnt[k]>maj[i][j].c)
					maj[i][j]={k, cnt[k]};
		}
}
int fucker_bound(int x, int val) {
	int l=0, r=v[x].size(), mid;
	while (l+1<r) {
		mid=l+r>>1;
		if (v[x][mid]<=val) l=mid;
		else r=mid;
	}
	return l;
}
int work(int l, int r, int ll, int rr, int &ans, int &val) {
	for (int i=l; i<=r; ++i) {
		int pos1=lower_bound(v[a[i]].begin(), v[a[i]].end(), ll)-v[a[i]].begin();
		int pos2=fucker_bound(a[i], rr);
		int tmp=pos2-pos1+1;
		if (tmp>val || (tmp==val && a[i]<ans))
			ans=a[i], val=tmp;
	}
}
int query(int l, int r) {
	int p=bel[l], q=bel[r];
	if (p==q) {
		int ans, val=0;
		work(l, r, l, r, ans, val);
		return ans;
	}
	int ans=maj[p+1][q-1].n, val=maj[p+1][q-1].c;
	work(l, L(p+1)-1, l, r, ans, val);
	work(R(q-1)+1, r, l, r, ans, val);
	return ans;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; ++i) cin >> a[i];
	init(); int x, y;
	while (m--) {
		cin >> x >> y;
		x=(x+ans-1)%n+1, y=(y+ans-1)%n+1;
		if (x>y) swap(x, y);
		ans=query(x, y);
		cout << ans << '\n';
	}
	return 0;
}