(当然还是可以过……)
代码就会变成这样子:
#include<bits/stdc++.h>
using namespace std;
inline bool rd ( int &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline bool lrd ( long long &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline void freo (){
freopen ( "data.in", "r", stdin );
freopen ( "data.out", "w", stdout );
}
const int LEN = 40001;
const int SQRT = 201;
int len, len_per, tot, mode [SQRT][SQRT], cnt [SQRT][LEN], order [LEN], belong [LEN];
int ranK [LEN], diff, raw [LEN], bound [SQRT][2], bucket [LEN];
bool compared [LEN];
inline void divide (){
len_per = sqrt ( len );
tot = ( len%len_per ? len/len_per+1 : len/len_per );
for ( int id = 1; id <= tot; ++id ){
bound [id][0] = (id-1)*len_per+1;
bound [id][1] = min ( id*len_per, len );
for ( int pos = bound [id][0]; pos <= bound [id][1]; ++pos )
belong [pos] = id;
}
}
inline void discrete (){
for ( int i = 1; i <= len; ++i ) order [i] = raw [i];
sort ( order+1, order+len +1 );
diff = unique ( order+1, order+len +1 ) -order-1;
for ( int pos = 1; pos <= len; ++pos )
ranK [pos] = lower_bound ( order+1, order+diff +1, raw [pos] ) - order;
}
inline void cal_cnt (){
for ( int id = 1; id <= tot; ++id ){
for ( int pos = bound [id][0]; pos <= bound [id][1]; ++pos )
cnt [id][ ranK[pos] ] ++;
for ( int number = 1; number <= diff; ++number )
cnt [id][number] += cnt [id-1][number];
}
}
inline void cal_mode (){
for ( int ida = 1; ida <= tot; ++ida ){ //id_a
for ( int idb = ida; idb <= tot; ++idb ){ //id_b
int temp_mode = mode [ida][idb-1];
for ( int pos = bound [idb][0]; pos <= bound [idb][1]; ++pos ){
int number = ranK [pos];
if (
( cnt[idb][number]-cnt[ida-1][number]>cnt[idb][temp_mode]-cnt[ida-1][temp_mode] ) ||
( cnt[idb][number]-cnt[ida-1][number]==cnt[idb][temp_mode]-cnt[ida-1][temp_mode] && number<temp_mode )
)
temp_mode = number;
}
mode [ida][idb] = temp_mode;
}
}
}
int main (){
int q; rd ( len ); rd ( q );
divide ();
for ( int i = 1; i <= len; ++i ) rd ( raw [i] );
discrete ();
cal_cnt ();
cal_mode ();
int uper = 0;
while ( q-- ){
int l_base, r_base; rd ( l_base ); rd ( r_base );
int l = ( l_base+uper-1+len )%len +1;
int r = ( r_base+uper-1+len )%len +1;
if ( l > r ) swap ( l, r );
int bl = belong [l], br = belong [r];
if ( br-bl <= 1 ){
for ( int pos = l; pos <= r; ++pos ){
compared [ ranK[pos] ] = false;
bucket [ ranK[pos] ]++;
}
int temp_mode = ranK [l];
int cnt_mode = bucket [temp_mode];
bucket [temp_mode] = 0;
compared [temp_mode] = true;
for ( int pos = l; pos <= r; ++pos ){
int number = ranK [pos];
if ( compared [number] ) continue;
compared [number] = true;
if ( bucket [number] > cnt_mode || ( bucket [number] == cnt_mode && number < temp_mode ) ){
temp_mode = number;
cnt_mode = bucket [number];
}
bucket [number] = 0;
}
printf ( "%d\n", order [temp_mode] );
uper = order [temp_mode];
}else{
for ( int pos = l; pos <= bound [bl][1]; ++pos ){
bucket [ ranK[pos] ] ++;
compared [ ranK[pos] ] = false;
}
for ( int pos = bound [br][0]; pos <= r; ++pos ){
bucket [ ranK[pos] ] ++;
compared [ ranK[pos] ] = false;
}
int temp_mode = mode [bl+1][br-1];
int cnt_mode = cnt [br-1][temp_mode] - cnt [bl][temp_mode] + bucket [temp_mode];
bucket [temp_mode] = 0;
compared [temp_mode] = true;
for ( int pos = l; pos <= bound [bl][1]; ++pos ){
int number = ranK [pos];
if ( compared [number] ) continue;
compared [number] = true;
if (
bucket[number]+cnt[br-1][number]-cnt[bl][number]>cnt_mode || (
bucket[number]+cnt[br-1][number]-cnt[bl][number]==cnt_mode && number<temp_mode )
){
temp_mode = number;
cnt_mode = bucket[number]+cnt[br-1][number]-cnt[bl][number];
}
bucket [number] = 0;
}
for ( int pos = bound [br][0]; pos <= r; ++pos ){
int number = ranK [pos];
if ( compared [number] ) continue;
compared [number] = true;
if (
bucket[number]+cnt[br-1][number]-cnt[bl][number]>cnt_mode || (
bucket[number]+cnt[br-1][number]-cnt[bl][number]==cnt_mode && number<temp_mode )
){
temp_mode = number;
cnt_mode = bucket[number]+cnt[br-1][number]-cnt[bl][number];
}
bucket [number] = 0;
}
printf ( "%d\n", order [temp_mode] );
uper = order [temp_mode];
}
}
return 0;
}
/*
6 3
1 2 3 2 1 2
1 5
3 6
1 5
1 2 1
*/