题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1493
差点被BZOJ上坑爹的剧透骗去写又长又丑的splay（虽然splay明显可写。。。），这题由于珠子的相对位置不变，所以可以用线段树维护，然后弄个delta维护一下在F过偶数次情况下的偏移量，dir维护F过的奇偶性，然后分类讨论就可以弄出对应左边在原项链中的位置，然后对于后面几个区间的操作注意顺逆时针的情况讨论，然后细节很多，写的时候多多注意。
代码（调了两个小时，尼玛要是在NOI赛场上怎么办啊。。。）：
#include <cstdio>
#include <cstring>
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define left( t ) t -> left
#define right( t ) t -> right
#define L( t ) t -> l
#define R( t ) t -> r
#define lc( t ) t -> lc
#define rc( t ) t -> rc
#define C( t ) t -> c
#define T( t ) t -> tag
int ch ;
void getint( int &t ) {
for ( ch = getchar( ) ; ch < '0' || ch > '9' ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t = 10 * t + ch - '0' ;
}
const int maxn = 501000 , maxv = 1510000 ;
inline void upd( int &x , int &y , int &z , int a , int b , int c ) {
z += c , z -= ( y == a ) ;
y = b ;
}
struct node {
node *left , *right ;
int l , r , lc , rc , c , tag ;
inline void pushdown( ) {
if ( tag ) {
lc = rc = tag , c = 1 ;
if ( l < r ) left -> tag = tag , right -> tag = tag ;
tag = 0 ;
}
}
inline void update( ) {
upd( lc = left -> lc , rc = left -> rc , c = left -> c , right -> lc , right -> rc , right -> c ) ;
}
} sgt[ maxv ] ;
typedef node* np ;
np pt = sgt , root ;
int n , c , col[ maxn ] , m ;
void build( int l , int r , np &t ) {
t = pt ++ ;
L( t ) = l , R( t ) = r , T( t ) = 0 ;
if ( l == r ) {
lc( t ) = rc( t ) = col[ l ] , C( t ) = 1 ;
return ;
}
int mid = ( l + r ) >> 1 ;
build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;
t -> update( ) ;
}
void change( int l , int r , int c , np t ) {
if ( l == L( t ) && r == R( t ) ) {
T( t ) = c ; return ;
}
t -> pushdown( ) ;
int mid = ( L( t ) + R( t ) ) >> 1 ;
if ( r <= mid ) change( l , r , c , left( t ) ) ; else
if ( l > mid ) change( l , r , c , right( t ) ) ; else {
change( l , mid , c , left( t ) ) , change( mid + 1 , r , c , right( t ) ) ;
}
left( t ) -> pushdown( ) , right( t ) -> pushdown( ) ; t -> update( ) ;
}
void query( int l , int r , int &x , int &y , int &z , np t ) {
t -> pushdown( ) ;
if ( l == L( t ) && r == R( t ) ) {
x = lc( t ) , y = rc( t ) , z = C( t ) ;
return ;
}
int mid = ( L( t ) + R( t ) ) >> 1 ;
if ( r <= mid ) query( l , r , x , y , z , left( t ) ) ; else
if ( l > mid ) query( l , r , x , y , z , right( t ) ) ; else {
int a , b , c ;
query( l , mid , x , y , z , left( t ) ) , query( mid + 1 , r , a , b , c , right( t ) ) ;
upd( x , y , z , a , b , c ) ;
}
}
int getcol( int pos , np t ) {
t -> pushdown( ) ;
if ( L( t ) == R( t ) ) return lc( t ) ;
int mid = ( L( t ) + R( t ) ) >> 1 ;
return getcol( pos , pos <= mid ? left( t ) : right( t ) ) ;
}
int delta = 0 , dir = 1 ;
inline void trans( int &pos ) {
if ( dir == 1 || pos == 1 ) {
pos -= delta ;
if ( pos <= 0 ) pos += n ;
} else {
pos = n - pos + 2 - delta ;
while ( pos <= 0 ) pos += n ;
while ( pos > n ) pos -= n ;
}
}
char s[ 10 ] ;
int main( ) {
getint( n ) , getint( c ) ;
rep( i , n ) getint( col[ i ] ) ;
build( 1 , n , root ) ;
getint( m ) ;
int x , y , z , a , b , c , i , j , k ;
while ( m -- ) {
scanf( "%s" , s ) ;
if ( s[ 0 ] == 'R' ) {
getint( a ) ;
delta = ( delta + a * dir + n ) % n ;
} else if ( s[ 0 ] == 'F' ) {
dir *= - 1 ;
} else if ( s[ 0 ] == 'S' ) {
getint( x ) , getint( y ) ;
trans( x ) , trans( y ) ;
a = getcol( x , root ) , b = getcol( y , root ) ;
change( x , x , b , root ) , change( y , y , a , root ) ;
} else if ( s[ 0 ] == 'P' ) {
getint( x ) , getint( y ) , getint( z ) ;
trans( x ) , trans( y ) ;
if ( x < y ) {
if ( dir == 1 ) change( x , y , z , root ) ; else {
change( 1 , x , z , root ) , change( y , n , z , root ) ;
}
} else if ( x > y ) {
if ( dir == - 1 ) change( y , x , z , root ) ; else {
change( 1 , y , z , root ) , change( x , n , z , root ) ;
}
} else change( x , x , z , root ) ;
} else if ( strlen( s ) == 1 ) {
query( 1 , n , x , y , z , root ) ;
if ( z == 1 ) printf( "%d\n" , 1 ) ; else printf( "%d\n" , z - ( x == y ) ) ;
} else {
getint( x ) , getint( y ) ;
trans( x ) , trans( y ) ;
if ( x < y ) {
if ( dir == 1 ) query( x , y , a , b , c , root ) ; else {
query( y , n , a , b , c , root ) , query( 1 , x , i , j , k , root ) ;
upd( a , b , c , i , j , k ) ;
}
} else if ( x > y ) {
if ( dir == - 1 ) query( y , x , a , b , c , root ) ; else {
query( x , n , a , b , c , root ) , query( 1 , y , i , j , k , root ) ;
upd( a , b , c , i , j , k ) ;
}
} else {
query( x , x , a , b , c , root ) ;
}
printf( "%d\n" , c ) ;
}
}
return 0 ;
}
网友评论