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

GreenCloudS

 
 
 

日志

 
 

2738: 矩阵乘法(梁 盾)(分块+主席树)  

2014-02-01 21:03:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


实在不想吐槽这个标题什么了,本来想找几道矩阵乘法的水题水水的,结果却成了裸数据结构。。。把X分成sqrt(n)个块,然后在没个块上面套棵主席树就可以啦~

空间复杂度:O( n ^ 2 log n )

时间复杂度:O( n ^ 2 log n + q sqrt( n ) log n )


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define MAXN 510

  • #define L( t ) sgt[ t ].left

  • #define R( t ) sgt[ t ].right

  • #define S( t ) sgt[ t ].size

  • #define MAXV 10001000

  • #define MAXM 30

  • #define check( ch ) ( ch >= '0' && ch <= '9' )

  •  

  • void getint( int &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {

  •         t *= 10 , t += ch - '0' ;

  •     }

  • }

  •  

  • int out[ 20 ] ;

  •  

  • void putint( int t ) {

  •     if ( ! t ) putchar( '0' ) ; else {

  •         out[ 0 ] = 0 ;

  •         for ( ; t ; t /= 10 ) out[ ++ out[ 0 ] ] = t % 10 ;

  •         while ( out[ 0 ] -- ) putchar( '0' + out[ out[ 0 ] + 1 ] ) ;

  •     }

  •     putchar( '\n' ) ;

  • }

  •  

  • struct node {

  •     int left , right , size ;

  •     node(  ) {

  •         left = right = size = 0 ;

  •     }

  • } sgt[ MAXV ] ;

  •  

  • int V = 0 ;

  •  

  • void Add( int l , int r , int k , int u , int &t ) {

  •     if ( ! t ) t = ++ V ;

  •     S( t ) = S( u ) + 1 ;

  •     if ( l == r ) return ;

  •     int mid = ( l + r ) >> 1 ;

  •     if ( k <= mid ) {

  •         R( t ) = R( u ) ; Add( l , mid , k , L( u ) , L( t ) ) ;

  •     } else {

  •         L( t ) = L( u ) ; Add( mid + 1 , r , k , R( u ) , R( t ) ) ;

  •     }

  • }

  •  

  • struct saver {

  •     int x , y , v ;

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

  •         return v < a.v ;

  •     }

  • } c[ MAXN * MAXN ] ;

  •  

  • int a[ MAXN ][ MAXN ] , n , N = 0 , b[ MAXN * MAXN ] , q , Rank[ MAXN ][ MAXN ] ;

  • int len ;

  • int Begin[ MAXM ] , End[ MAXM ] , M , block[ MAXM ][ MAXN ] , pre[ MAXN ][ MAXN ] ;

  •  

  • void Init(  ) {

  •     getint( n ) , getint( q ) ;

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

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

  •             getint( a[ i ][ j ] ) ;

  •             c[ ++ N ].v = a[ i ][ j ] ;

  •             c[ N ].x = i , c[ N ].y = j ;

  •         }

  •     }

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

  •     N = 0 ;

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

  •         if ( i == 1 || c[ i ].v != c[ i - 1 ].v ) b[ ++ N ] = c[ i ].v ;

  •         Rank[ c[ i ].x ][ c[ i ].y ] = N ;

  •     }

  •     len = int( sqrt( n ) ) ; M = n / len ;

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

  •         Begin[ i ] = ( i - 1 ) * len + 1 , End[ i ] = i * len ;

  •     }

  •     if ( M * len < n ) {

  •         Begin[ M + 1 ] = M * len + 1 , End[ M + 1 ] = n ;

  •         ++ M ;

  •     }

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

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

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

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

  •             Add( 1 , N , Rank[ i ][ j ] , pre[ i ][ j - 1 ] , pre[ i ][ j ] ) ;

  •         }

  •     }

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

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

  •             int temp = block[ i ][ j - 1 ] ;

  •             for ( int k = Begin[ i ] ; k <= End[ i ] ; ++ k ) {

  •                 int rec = 0 ;

  •                 Add( 1 , N , Rank[ k ][ j ] , temp , rec ) ;

  •                 temp = rec ;

  •             }

  •             block[ i ][ j ] = temp ;

  •         }

  •     }

  • }

  •  

  • int range[ MAXN * MAXN ][ 2 ] , rn = 0 ;

  •  

  • void getrange( int x1 , int x2 , int y1 , int y2 ) {

  •     int pos1 = ( x1 - 1 ) / len + 1 , pos2 = ( x2 - 1 ) / len + 1 ;

  •     rn = 0 ;

  •     if ( pos1 == pos2 ) {

  •         if ( x1 == Begin[ pos1 ] && x2 == End[ pos1 ] ) {

  •             range[ ++ rn ][ 0 ] = block[ pos1 ][ y2 ] ;

  •             range[ rn ][ 1 ] = block[ pos1 ][ y1 - 1 ] ;

  •         } else {

  •             for ( int i = x1 ; i <= x2 ; ++ i ) {

  •                 range[ ++ rn ][ 0 ] = pre[ i ][ y2 ] ;

  •                 range[ rn ][ 1 ] = pre[ i ][ y1 - 1 ] ;

  •             }

  •         }

  •     } else {

  •         for ( int i = x1 ; i <= End[ pos1 ] ; ++ i ) {

  •             range[ ++ rn ][ 0 ] = pre[ i ][ y2 ] ;

  •             range[ rn ][ 1 ] = pre[ i ][ y1 - 1 ] ;

  •         }

  •         for ( int i = Begin[ pos2 ] ; i <= x2 ; ++ i ) {

  •             range[ ++ rn ][ 0 ] = pre[ i ][ y2 ] ;

  •             range[ rn ][ 1 ] = pre[ i ][ y1 - 1 ] ;

  •         }

  •         if ( ( ++ pos1 ) <= ( -- pos2 ) ) {

  •             for ( int i = pos1 ; i <= pos2 ; ++ i ) {

  •                 range[ ++ rn ][ 0 ] = block[ i ][ y2 ] ;

  •                 range[ rn ][ 1 ] = block[ i ][ y1 - 1 ] ;

  •             }

  •         }

  •     }

  • }

  •  

  • int query( int x1 , int x2 , int y1 , int y2 , int k ) {

  •     getrange( x1 , x2 , y1 , y2 ) ;

  •     int l = 1 , r = N ;

  •     while ( l < r ) {

  •         int mid = ( l + r ) >> 1 , sum = 0 ;

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

  •             sum += S( L( range[ i ][ 0 ] ) ) , sum -= S( L( range[ i ][ 1 ] ) ) ;

  •         }

  •         if ( k <= sum ) {

  •             r = mid ;

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

  •                 range[ i ][ 0 ] = L( range[ i ][ 0 ] ) ;

  •                 range[ i ][ 1 ] = L( range[ i ][ 1 ] ) ;

  •             }

  •         } else {

  •             l = mid + 1 , k -= sum ;

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

  •                 range[ i ][ 0 ] = R( range[ i ][ 0 ] ) ;

  •                 range[ i ][ 1 ] = R( range[ i ][ 1 ] ) ;

  •             }

  •         }

  •     }

  •     return b[ l ] ;

  • }

  •  

  • void Solve(  ) {

  •     while ( q -- ) {

  •         int x1 , y1 , x2 , y2 , k ;

  •         getint( x1 ) , getint( y1 ) , getint( x2 ) , getint( y2 ) ;

  •         getint( k ) ;

  •         putint( query( x1 , x2 , y1 , y2 , k ) ) ;

  •     }

  • }

  •  

  • int main(  ) {

  •     Init(  ) ;

  •     Solve(  ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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