传送门

solution：分块+二分：

先离散化，再预处理出第i块到第j块众数

然后用分块乱搞就AC了

/**************************************************************Problem: 2724User: VenishelLanguage: C++Result: AcceptedTime:17864 msMemory:4300 kb ****************************************************************/#include <cmath>
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;#define N 50007
#define cls(a,b) memset( a, b, sizeof(a));
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int bl[N], v[N], val[N], cnt[N];
int aa[500][500];
vector<int> ve[N];
map<int, int> mp;
int n, m, blk, tot;inline void pre_wkg( int x ){cls(cnt, 0);int mx = 0, ret = 0;for ( int i = (x-1)*blk+1; i <= n; i++ ){cnt[v[i]]++;int t = bl[i];if ( cnt[v[i]] > mx || ( cnt[v[i]] == mx && val[v[i]] < val[ret] ) ) mx = cnt[v[i]], ret = v[i];aa[x][t] = ret;}
}inline int query_num( int l, int r, int x ){int rt = upper_bound( ve[x].begin(), ve[x].end(), r) - lower_bound( ve[x].begin(), ve[x].end(), l );return rt;
}inline int query_ans( int a, int b ){int ret = 0, mx = 0;ret = aa[ bl[a] + 1 ][ bl[b] - 1 ];mx = query_num( a, b, ret );for ( int i = a; i <= min(b, bl[a]*blk); i++ ){int t = query_num( a, b, v[i] );if ( mx < t || ( t == mx && val[v[i]] < val[ret] ) ) ret = v[i], mx = t;}if ( bl[a] != bl[b] ){for ( int i = (bl[b]-1)*blk+1; i <= b; i++ ){int t = query_num( a, b, v[i] );if ( mx < t || ( t == mx && val[v[i]] < val[ret])) mx = t, ret = v[i];}}return ret;
}int main(){n = read(), m = read();blk = 205, tot = 0;for ( int i = 1; i <= n; i++ ){v[i] = read();if ( !mp[v[i]] ) mp[v[i]] = ++tot, val[tot] = v[i];v[i] = mp[v[i]];ve[v[i]].push_back(i);}for ( int i = 1; i <= n; i++ ) bl[i] = (i-1)/blk + 1;for ( int i = 1; i <= bl[n]; i++ ) pre_wkg( i );int ret = 0;for ( int i = 1; i <= m; i++){int l, r;l = read(), r = read();l = (l+ret-1) % n + 1, r = (r+ret-1) % n + 1;if ( l > r ) swap( l, r );printf( "%d\n", ret = val[query_ans( l, r )] );}return 0;
}