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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3262: 陌上花开(BIT+Treap)  

2014-06-10 21:48:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


额。。。剧透太无聊了额。。。排序一下搞掉一维,然后一维BIT,套一维Treap维护即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • using namespace std ;

  •  

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  •  

  • #define lowbit( x ) ( ( - x ) & x )

  •  

  • const int maxn = 101000 ;

  • const int maxv = 4010000 ;

  • const int maxk = 201000 ;

  •  

  • struct node {

  •      

  •     node *lc , *rc ;

  •     int p , k , s ;

  •      

  •     inline void update(  ) {

  •         s = lc -> s + rc -> s + 1 ;

  •     }

  •      

  • } V[ maxv ] ;

  •  

  • typedef node* np ;

  •  

  • np root[ maxk ] , pt = V , null = V ;

  • int N , K , ans[ maxn ] ;

  •  

  • inline void Left( np &t ) {

  •     np k = t -> rc ;

  •     t -> rc = k -> lc ; t -> update(  ) ;

  •     k -> lc = t ; k -> update(  ) ;

  •     t = k ;

  • }

  •  

  • inline void Right( np &t ) {

  •     np k = t -> lc ;

  •     t -> lc = k -> rc ; t -> update(  ) ;

  •     k -> rc = t ; k -> update(  ) ;

  •     t = k ;

  • }

  •  

  • void Insert( int k , np &t ) {

  •     if ( t == null ) {

  •         pt -> lc = pt -> rc = null , pt -> s = 1 , pt -> k = k , pt -> p = rand(  ) ;

  •         t = pt ++ ;

  •         return ;

  •     }

  •     ++ t -> s ;

  •     if ( k < t -> k ) {

  •         Insert( k , t -> lc ) ;

  •         if ( t -> lc -> p > t -> p ) Right( t ) ;

  •     } else {

  •         Insert( k , t -> rc ) ;

  •         if ( t -> rc -> p > t -> p ) Left( t ) ;

  •     }

  • }

  •  

  • inline int Rank( int k , np t ) {

  •     int rec = 0 ;

  •     for ( ; t != null ; ) {

  •         if ( t -> k <= k ) {

  •             rec += ( 1 + t -> lc -> s ) ; t = t -> rc ;

  •         } else t = t -> lc ;

  •     }

  •     return rec ;

  • }

  •  

  • struct ntype {

  •      

  •     int x , y , z ;

  •      

  •     inline void Read(  ) {

  •         scanf( "%d%d%d" , &x , &y , &z ) ;

  •     }

  •      

  •     bool operator < ( const ntype &a ) const {

  •         return x < a.x ;

  •     }

  •      

  • } num[ maxn ] ;

  •  

  • inline void Init(  ) {

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

  •     srand( 1221 ) , ++ pt ;

  •     null -> lc = null -> rc = null , null -> s = null -> p = null -> k = 0 ;

  •     rep( i , K ) root[ i ] = null ;

  •     rep( i , N ) num[ i ].Read(  ) ;

  • }

  •  

  • inline void Add( int p , int v ) {

  •     for ( ; p <= K ; p += lowbit( p ) ) Insert( v , root[ p ] ) ;

  • }

  •  

  • inline int Query( int p , int v ) {

  •     int rec = 0 ;

  •     for ( ; p ; p -= lowbit( p ) ) rec += Rank( v , root[ p ] ) ;

  •     return rec ;

  • }

  •  

  • inline void Solve(  ) {

  •     sort( num + 1 , num + N + 1 ) ;

  •     for ( int l = 1 , r ; l <= N ; l = r + 1 ) {

  •         for ( r = l ; r < N && num[ r + 1 ].x == num[ r ].x ; ++ r ) ;

  •         REP( i , l , r ) Add( num[ i ].y , num[ i ].z ) ;

  •         REP( i , l , r ) ans[ Query( num[ i ].y , num[ i ].z ) ] ++ ;

  •     }

  • }

  •  

  • int main(  ) {

  •     Init(  ) ;

  •     Solve(  ) ;

  •     rep( i , N ) printf( "%d\n" , ans[ i ] ) ;

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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