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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1483: [HNOI2009]梦幻布丁(区间树启发式合并)  

2014-03-10 14:05:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1483


区间树跟线段树是两回事额,区间树说白了就是一颗维护有序的区间平衡树,这道题就是每种颜色上面用区间树维护对应的区间,然后每次修改颜色就把对应的区间树合并即可,记得如果前后缀跟要插入的区间可以合并那么就合并掉。


代码(Treap):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • using namespace std ;

  •  

  • #define update( t S( t )=S(L( t ))+S(R( t ))+1

  •  

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define S( t ) size[ t ]

  • #define K( t ) key[ t ]

  • #define P( t ) priority[ t ]

  •  

  • const int inf =0x7fffffff;

  • const int maxn =100010;

  • const int maxc =1000100;

  •  

  • struct seg{

  •  

  •     int l , r ;

  •  

  •     bool operator<(const seg &)const{

  •         return l < a.;

  •     }

  •     bool operator==(const seg &)const{

  •         return l == a.;

  •     }

  •     bool operator>(const seg &)const{

  •         return l > a.;

  •     }

  •  

  •     void oper(int _l ,int _r ){

  •         l = _l , r = _r ;

  •     }

  •  

  • } key[ maxn ];

  •  

  • int left[ maxn ], right[ maxn ], size[ maxn ], priority[ maxn ], V =0;

  •  

  • void Init_treap(  ){

  •     L(0)=R(0)=S(0)=0,P(0)=- inf ;

  •     srand(12);

  • }

  •  

  • void Left(int&){

  •     int k =R( t );

  •     R( t )=L( k );update( t );

  •     L( k )= t ;update( k );

  •     t = k ;

  • }

  •  

  • void Right(int&){

  •     int k =L( t );

  •     L( t )=R( k );update( t );

  •     R( k )= t ;update( k );

  •     t = k ;

  • }

  •  

  • int make( seg value ){

  •     L(++ V )=0;R( V )=0,S( V )=1,P( V )=rand(  ),K( V )= value ;

  •     return V ;

  • }

  •  

  • void Insert(int v ,int&){

  •     if(! t ){

  •         t = v ;return;

  •     }

  •     if(K( v )<K( t )){

  •         Insert( v ,L( t ));update( t );

  •         if(P(L( t ))>P( t ))Right( t );

  •     }else{

  •         Insert( v ,R( t ));update( t );

  •         if(P(R( t ))>P( t ))Left( t );

  •     }

  • }

  •  

  • void Delete( seg k ,int&){

  •     if( k ==K( t )){

  •         if(!L( t )){

  •             t =R( t );return;

  •         }else if(!R( t )){

  •             t =L( t );return;

  •         }else{

  •             if(P(L( t ))>P(R( t ))){

  •                 Right( t );Delete( k ,R( t ));

  •             }else{

  •                 Left( t );Delete( k ,L( t ));

  •             }

  •         }

  •     }else Delete( k , k <K( t )?L( t ):R( t ));

  •     update( t );

  • }

  •  

  • seg Prefix( seg k ,int t ){

  •     seg ret ; ret.oper(- inf ,- inf );

  •     for(; t ; t = k >K( t )?R( t ):L( t )){

  •         if(K( t )< k ) ret =max( ret ,K( t ));

  •     }

  •     return ret ;

  • }

  •  

  • seg Suffix( seg k ,int t ){

  •     seg ret ; ret.oper( inf , inf );

  •     for(; t ; t = k <K( t )?L( t ):R( t )){

  •         if(K( t )> k ) ret =min( ret ,K( t ));

  •     }

  •     return ret ;

  • }

  •  

  • int b[ maxn ], bn ;

  •  

  • void dfs(int t ){

  •     if(L( t ))dfs(L( t ));

  •     b[++ bn ]= t ;

  •     if(R( t ))dfs(R( t ));

  • }

  •  

  • int cnt =0;

  •  

  • int merge(int v ,int u ){

  •     if(! v )return u ;

  •     if(! u )return v ;

  •     if(S( v )>S( u ))swap( v , u );

  •     bn =0;

  •     dfs( v );

  •     for(int i =1; i <= bn ;++ i ){

  •         L( b[ i ])=R( b[ i ])=0,S( b[ i ])=1,P( b[ i ])=rand(  );

  •         seg pre =Prefix(K( b[ i ]), u ), suff =Suffix(K( b[ i ]), u );

  •         if(K( b[ i ]).== pre.+1){

  •             Delete( pre , u );

  •             K( b[ i ]).= pre.;

  •             -- cnt ;

  •         }

  •         if(K( b[ i ]).== suff.-1){

  •             Delete( suff , u );

  •             K( b[ i ]).= suff.;

  •             -- cnt ;

  •         }

  •         Insert( b[ i ], u );

  •     }

  •     return u ;

  • }

  •  

  • int roof[ maxc ], n , m , a[ maxn ];

  •  

  • int main(  ){

  •     memset( roof ,0,sizeof( roof ));

  •     Init_treap(  );

  •     scanf("%d%d",&,&);

  •     for(int i =0; i ++< n ;)scanf("%d", a + i );

  •     seg ret ;

  •     for(int i =0; i ++< n ;){

  •         if( i ==1|| a[ i ]!= a[ i -1]) ret.= i ;

  •         if( i == n || a[ i +1]!= a[ i ]){

  •             ret.= i ,++ cnt ;

  •             Insert(make( ret ), roof[ a[ i ]]);

  •         }

  •     }

  •     while( m --){

  •         int x ;scanf("%d",&);

  •         if( x ==1){

  •             int c0 , c1 ;scanf("%d%d",&c0 ,&c1 );

  •             if( c0 != c1 ){

  •                 roof[ c1 ]=merge( roof[ c0 ], roof[ c1 ]);

  •                 roof[ c0 ]=0;

  •             }

  •         }else printf("%d\n", cnt );

  •     }

  •     return 0;

  • }



  评论这张
 
阅读(1)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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