题目：http://www.lydsy.com/JudgeOnline/problem.php?id=272
大意：区间众数，强制在线。至于题解，Violet6的解题报告已经够详细的了，就不班门弄斧了额。
代码（我写的是第二种写法O(n sqrt(n) log n)，结果无限TLE，在N次常数优化之后终于AC了饿）：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std ;
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define MAXN 40100
#define inf 0x7fffffff
#define MAXB 410
#define check( ch ) ( ch >= '0' && ch <= '9' )
void getint( int &t ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; check( ch ) ; ch = getchar( ) ) {
t *= 10 ; t += ch - '0' ;
}
}
int w[ 20 ] ;
void putint( int t ) {
if ( ! t ) putchar( '0' ) ; else {
w[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) w[ ++ w[ 0 ] ] = t % 10 ;
while ( w[ 0 ] -- ) putchar( '0' + w[ w[ 0 ] + 1 ] ) ;
}
putchar( '\n' ) ;
}
struct saver {
int v , t ;
bool operator < ( const saver &a ) const {
return v < a.v || ( v == a.v && t < a.t ) ;
}
bool operator == ( const saver &a ) const {
return v == a.v && t == a.t ;
}
bool operator > ( const saver &a ) const {
return v > a.v || ( v == a.v && t > a.t ) ;
}
} b[ MAXN ] ;
int N , first[ MAXN ] , last[ MAXN ] , Mn ;
saver make( int v , int t ) {
saver u ;
u.v = v , u.t = t ;
return u ;
}
int Lower( int l , int r , saver v ) {
l -- , ++ r ;
while ( r - l > 1 ) {
int mid = ( l + r ) >> 1 ;
if ( b[ mid ] < v ) l = mid ; else r = mid ;
}
return r ;
}
int Upper( int l , int r , saver v ) {
l -- , ++ r ;
while ( r - l > 1 ) {
int mid = ( l + r ) >> 1 ;
if ( b[ mid ] > v ) r = mid ; else l = mid ;
}
return r ;
}
int COUNT( int l , int r , int v , int L , int R ) {
return Upper( L , R , make( v , r ) ) - Lower( L , R , make( v , l ) ) ;
}
int n , m , M , a[ MAXN ] ;
int Begin[ MAXB ] , End[ MAXB ] , Ans[ MAXB ][ MAXB ] ;
void INIT( ) {
int ret = int( sqrt( n ) ) ;
rep( i , ret ) {
Begin[ i ] = ( i - 1 ) * ret + 1 ;
End[ i ] = i * ret ;
}
if ( ret * ret < n ) {
M = ret + 1 ;
Begin[ M ] = ret * ret + 1 ;
End[ M ] = n ;
} else M = ret ;
rep( i , M ) {
int ans , rec = - inf ;
for ( int j = i ; j <= M ; ++ j ) {
for ( int k = Begin[ j ] ; k <= End[ j ] ; ++ k ) {
int cnt = COUNT( Begin[ i ] , k , a[ k ] , first[ k ] , last[ k ] ) ;
if ( cnt > rec || ( cnt == rec && a[ k ] < ans ) ) {
ans = a[ k ] , rec = cnt ;
}
}
Ans[ i ][ j ] = ans ;
}
}
}
int Query( int l , int r ) {
int ans = 0 , rec = - inf , L , R , ret = int( sqrt( n ) ) ;
L = ( l - 1 ) / ret + 1 , R = ( r - 1 ) / ret + 1 ;
if ( L + 1 <= R - 1 ) {
if ( ans == Ans[ L + 1 ][ R - 1 ] ) return ans ;
int cnt = COUNT( l , r , Ans[ L + 1 ][ R - 1 ] , 1 , N ) ;
if ( cnt > rec || ( cnt == rec && Ans[ L + 1 ][ R - 1 ] < ans ) ) {
rec = cnt , ans = Ans[ L + 1 ][ R - 1 ] ;
}
}
if ( L == R ) {
for ( int i = l ; i <= r ; ++ i ) {
if ( a[ i ] == ans ) continue ;
int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;
if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {
rec = cnt , ans = a[ i ] ;
}
}
} else {
for ( int i = l ; i <= End[ L ] ; ++ i ) {
if ( a[ i ] == ans ) continue ;
int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;
if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {
rec = cnt , ans = a[ i ] ;
}
}
for ( int i = Begin[ R ] ; i <= r ; ++ i ) {
if ( a[ i ] == ans ) continue ;
int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;
if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {
rec = cnt , ans = a[ i ] ;
}
}
}
return ans ;
}
int main( ) {
getint( n ) , getint( m ) ;
rep( i , n ) {
getint( a[ i ] ) ;
b[ i ].v = a[ i ] , b[ i ].t = i ;
}
N = n + 2 ;
b[ n + 1 ].v = 0 , b[ n + 1 ].t = 0 ;
b[ N ].v = inf , b[ N ].t = inf ;
sort( b + 1 , b + N + 1 ) ;
for ( int i = 0 ; i ++ < N ; ) {
if ( i == 1 || b[ i ].v != b[ i - 1 ].v ) Mn = i ;
first[ b[ i ].t ] = Mn ;
}
for ( int i = N ; i ; -- i ) {
if ( i == N || b[ i ].v != b[ i + 1 ].v ) Mn = i ;
last[ b[ i ].t ] = Mn ;
}
INIT( ) ;
int ans = 0 ;
while ( m -- ) {
int l , r ; getint( l ) , getint( r ) ;
l = ( l + ans - 1 ) % n + 1 , r = ( r + ans - 1 ) % n + 1 ;
if ( l > r ) swap( l , r ) ;
putint( ans = Query( l , r ) ) ;
}
return 0 ;
}
网友评论