题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3489
昨天脑子晒得有点残了，所以发上来的题解也相当暴力额。。
首先对于设位置在pos的数前面的第一个与他相同的数位置是pre（不存在则为0），后面第一个与他位置相同的数位置是suff（不存在则为n+1）的话，那么这题就是在找一个数对（pre,pos,suff）其中0<=pre<l , l<=pos<=r , r<suff<=n+1，且要求value（pos）最大，那么又考虑到pre是从0开始记的，那么我们就以pre建立一串类似前缀和的持久化二维线段树维护最大值即可。
代码（反正我写残了，基本就是卡着过掉的额）：
b999a9014c086e06e4b42eee00087bf40ad1cb73.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std ;
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
const int maxvx = 3001000 ;
const int maxvy = 40010000 ;
const int maxn = 100100 ;
struct point {
int x , y ;
point( int _x , int _y ) : x( _x ) , y( _y ) {
}
};
struct nodey {
int left , right , Max ;
nodey( ) {
left = right = Max = 0 ;
}
} sgty[ maxvy ] ;
struct nodex {
int left , right , sgt ;
nodex( ) {
left = right = sgt = 0 ;
}
} sgtx[ maxvx ] ;
int vx = 0 , vy = 0 ;
int n , m , a[ maxn ] ;
void addy( int pos , int value , int l , int r , int u , int &t ) {
if ( ! t ) t = ++ vy ;
sgty[ t ].Max = max( sgty[ u ].Max , value ) ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
if ( pos <= mid ) {
sgty[ t ].right = sgty[ u ].right ;
addy( pos , value , l , mid , sgty[ u ].left , sgty[ t ].left ) ;
} else {
sgty[ t ].left = sgty[ u ].left ;
addy( pos , value , mid + 1 , r , sgty[ u ].right , sgty[ t ].right ) ;
}
}
int queryy( int l , int r , int _l , int _r , int t ) {
if ( ! t ) return 0 ;
if ( l == _l && r == _r ) return sgty[ t ].Max ;
int mid = ( _l + _r ) >> 1 ;
if ( r <= mid ) return queryy( l , r , _l , mid , sgty[ t ].left ) ;
if ( l > mid ) return queryy( l , r , mid + 1 , _r , sgty[ t ].right ) ;
return max( queryy( l , mid , _l , mid , sgty[ t ].left ) , queryy( mid + 1 , r , mid + 1 , _r , sgty[ t ].right ) ) ;
}
void addx( point pos , int value , int l , int r , int u , int &t ) {
if ( ! t ) t = ++ vx ;
addy( pos.y , value , 0 , n + 1 , sgtx[ u ].sgt , sgtx[ t ].sgt ) ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
if ( pos.x <= mid ) {
sgtx[ t ].right = sgtx[ u ].right ;
addx( pos , value , l , mid , sgtx[ u ].left , sgtx[ t ].left ) ;
} else {
sgtx[ t ].left = sgtx[ u ].left ;
addx( pos , value , mid + 1 , r , sgtx[ u ].right , sgtx[ t ].right ) ;
}
}
int queryx( point l , point r , int _l , int _r , int t ) {
if ( ! t ) return 0 ;
if ( l.x == _l && r.x == _r ) return queryy( l.y , r.y , 0 , n + 1 , sgtx[ t ].sgt ) ;
int mid = ( _l + _r ) >> 1 ;
if ( r.x <= mid ) return queryx( l , r , _l , mid , sgtx[ t ].left ) ;
if ( l.x > mid ) return queryx( l , r , mid + 1 , _r , sgtx[ t ].right ) ;
int templ = queryx( l , point( mid , r.y ) , _l , mid , sgtx[ t ].left ) ;
int tempr = queryx( point( mid + 1 , l.y ) , r , mid + 1 , _r , sgtx[ t ].right ) ;
return max( templ , tempr ) ;
}
struct Num {
int pos , value ;
void oper( int _pos , int _value ) {
pos = _pos , value = _value ;
}
bool operator < ( const Num &a ) const {
return value < a.value || ( value == a.value && pos < a.pos ) ;
}
} b[ maxn << 2 ] ;
int N = 0 ;
vector < point > ve[ maxn ] ;
bool used[ maxn ] ;
typedef vector < point > :: iterator P ;
int Pre[ maxn ] ;
int query( int l , int r ) {
return queryx( point( l , r + 1 ) , point( r , n + 1 ) , 1 , n , Pre[ l ] ) ;
}
int main( ) {
scanf( "%d%d" , &n , &m ) ;
memset( used , false , sizeof( used ) ) ;
rep( i , n ) {
scanf( "%d" , a + i ) ;
if ( ! used[ a[ i ] ] ) {
used[ a[ i ] ] = true ;
b[ ++ N ].oper( 0 , a[ i ] ) ;
b[ ++ N ].oper( n + 1 , a[ i ] ) ;
}
b[ ++ N ].oper( i , a[ i ] ) ;
}
sort( b + 1 , b + N + 1 ) ;
rep( i , N ) if ( i > 1 && i < N && b[ i ].value == b[ i - 1 ].value && b[ i ].value == b[ i + 1 ].value ) {
ve[ b[ i - 1 ].pos + 1 ].push_back( point( b[ i ].pos , b[ i + 1 ].pos ) ) ;
}
Pre[ 0 ] = 0 ;
rep( i , n ) {
Pre[ i ] = Pre[ i - 1 ] ;
int temp ;
for ( P p = ve[ i ].begin( ) ; p != ve[ i ].end( ) ; ++ p ) {
temp = 0 ;
addx( *p , a[ p -> x ] , 1 , n , Pre[ i ] , temp ) ;
Pre[ i ] = temp ;
}
}
int last = 0 ;
while ( m -- ) {
int x , y , l , r ; scanf( "%d%d" , &x , &y ) ;
l = ( x + last ) % n + 1 , r = ( y + last ) % n + 1 ;
if ( l > r ) swap( l , r ) ;
printf( "%d\n" , last = query( l , r ) ) ;
}
return 0 ;
}
网友评论