学步园

传送门：【BZOJ】1493 [NOI2007]项链工厂

题目分析：今天不适合做题！不对。。。是昨天。。

这题可以用线段树来做，只要每次R x的时候维护位移，然后F就维护是否旋转，然后需要用到L,R时就转化为L,R实际应该在的位置，线段树搞搞好了。需要注意的是，如果是询问C且整串为一种颜色应该输出1。

写这题的时候真是逗的不行了。。CS i j询问的是一个段，然后我以为如果j+1==i则就和C一样了。。。我说为什么不考虑这个就能过。。考虑了就wa。。T U T

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n
#define rt o , l , r

const int MAXN = 500005 ;

int lnum[MAXN << 2] , rnum[MAXN << 2] ;
int set[MAXN << 2] , sum[MAXN << 2] ;
int n , q ;
bool rev ;
int move ;
char op[5] ;

void pushup ( int o ) {
	sum[o] = sum[ls] + sum[rs] ;
	lnum[o] = lnum[ls] ;
	rnum[o] = rnum[rs] ;
	if ( rnum[ls] == lnum[rs] ) -- sum[o] ;
}

void pushdown ( int o ) {
	if ( set[o] ) {
		sum[ls] = sum[rs] = 1 ;
		lnum[ls] = rnum[ls] = set[o] ;
		lnum[rs] = rnum[rs] = set[o] ;
		set[ls] = set[rs] = set[o] ;
		set[o] = 0 ;
	}
}

void update ( int L , int R , int v , int o , int l , int r ) {
	if ( L <= l && r <= R ) {
		sum[o] = 1 ;
		set[o] = v ;
		lnum[o] = rnum[o] = v ;
		return ;
	}
	int m = mid ;
	pushdown ( o ) ;
	if ( L <= m ) update ( L , R , v , lson ) ;
	if ( m <  R ) update ( L , R , v , rson ) ;
	pushup ( o ) ;
}

int query ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return sum[o] ;
	int m = mid ;
	pushdown ( o ) ;
	if ( R <= m ) return query ( L , R , lson ) ;
	if ( m <  L ) return query ( L , R , rson ) ;
	return query ( L , R , lson ) + query ( L , R , rson ) - ( rnum[ls] == lnum[rs] ) ;
}

int query_color ( int pos , int o , int l , int r ) {
    while ( l != r ) {
        int m = mid ;
        pushdown ( o ) ;
        if ( pos <= m ) {
            r = m ;
            o = ls ;
        } else {
            l = m + 1 ;
            o = rs ;
        }
    }
    return lnum[o] ;
}

void build ( int o , int l , int r ) {
	set[o] = 0 ;
	if ( l == r ) {
		scanf ( "%d" , &lnum[o] ) ;
		rnum[o] = lnum[o] ;
		sum[o] = 1 ;
		return ;
	}
	int m = mid ;
	build ( lson ) ;
	build ( rson ) ;
	pushup ( o ) ;
}

void maintain ( int& L , int& R ) {
	if ( rev ) {
		L = ( 2 * n - move - L + 1 ) % n + 1 ;
		R = ( 2 * n - move - R + 1 ) % n + 1 ;
		swap ( L , R ) ;
	} else {
		L = ( L - move + n - 1 ) % n + 1 ;
		R = ( R - move + n - 1 ) % n + 1 ;
	}
}

void scanf ( int&x , char c = 0 ) {
    while ( ( c = getchar () ) < '0' || c > '9' ) ;
    x = c - '0' ;
    while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}

void solve () {
	int L , R , v , ans ;
	move = rev = 0 ;
	scanf ( "%d%*d" , &n ) ;
	build ( root ) ;
	scanf ( "%d" , &q ) ;
	while ( q -- ) {
		scanf ( "%s" , op ) ;
		if ( op[1] == 'S' ) {
			scanf ( L ) , scanf ( R ) ;
			maintain ( L , R ) ;
			//printf ( "%d %d\n" , L , R ) ;
			if ( L <= R ) ans = query ( L , R , root ) ;
			else {
				ans = query ( 1 , R , root ) + query ( L , n , root ) ;
				if ( rnum[1] == lnum[1] ) -- ans ;
			}
			printf ( "%d\n" , ans ) ;
		}
		else if ( op[0] == 'R' ) {
			scanf ( v ) ;
			if ( rev ) move = ( move - v + n ) % n ;
			else move = ( move + v ) % n ;
		}
		else if ( op[0] == 'F' ) rev ^= 1 ;
		else if ( op[0] == 'S' ) {
			scanf ( L ) , scanf ( R ) ;
			maintain ( L , R ) ;
			//printf ("swap : %d %d\n" , L , R ) ;
			int Lv = query_color ( L , root ) ;
			int Rv = query_color ( R , root ) ;
			update ( L , L , Rv , root ) ;
			update ( R , R , Lv , root ) ;
		}
		else if ( op[0] == 'P' ) {
			scanf ( L ) , scanf ( R ) , scanf ( v ) ;
			maintain ( L , R ) ;
			if ( L <= R ) update ( L , R , v , root ) ;
			else update ( 1 , R , v , root ) , update ( L , n , v , root ) ;
		}
		else printf ( "%d\n" , sum[1] - ( lnum[1] == rnum[1] && sum[1] > 1 ) ) ;
	}
}

int main () {
	//freopen ( "necklace.in" , "r" , stdin ) ;
	//freopen ( "necklace.out" , "w" , stdout ) ;
	solve () ;
	return 0 ;
}