注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1493: [NOI2007]项链工厂(线段树)  

2014-05-26 16:58:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ;

}


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017