本文主要是介绍UVa 11992 Fast Matrix Operations 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVa 11992 Fast Matrix Operations
题目大意：有一个r行c列的全0矩阵，支持三种操作：
1 x1 y1 x2 y2 v 子矩阵(x1，y1，x2，y2)的所有元素增加v（v > 0）。
2 x1 y1 x2 y2 v 子矩阵(x1，y1，x2，y2)的所有元素设为v（v > 0）。
3 x1 y1 x2 y2 查询子矩阵(x1，y1，x2，y2)的元素和、最小值和最大值。
子矩阵(x1，y1，x2，y2)是指满足x1 <= x <= x2，y1 <= y <= y2，的所有元素(x，y)。输入保证任何时刻矩阵内的所有元素之和不超过10 ^ 9。
其中，矩阵不超过20行，元素总数不超过10 ^ 6，且操作数不超过20000。
题目分析：
本题即区间修改，区间查询问题。
本来是想写一棵树套树的。。不过发现实在是写不出来，不会写QAQ，然后转头扑倒一维线段树。
矩阵不超过20行，所以我们可以为每行建一棵线段树，则本题便可以化为一维线段树。
其他的就注意一下值的传递即可。
代码如下：
#include <cstdio>
#include <cstring>#define clear( A , X ) memset ( A , X , sizeof A )
#define lson l , m , o << 1
#define rson m + 1 , r , o << 1 | 1const int maxR = 22 ;
const int maxC = 200005 ;
const int oo = 0x3f3f3f3f ;int max[maxR][maxC] , min[maxR][maxC] , sum[maxR][maxC] ;
int add[maxR][maxC] , set[maxR][maxC] ;int Min ( const int X , const int Y ) {if ( X < Y ) return X ;return Y ;
}int Max ( const int X , const int Y ) {if ( X > Y ) return X ; return Y ;
}void PushUp ( int x , int o ) {sum[x][o] = sum[x][o << 1] + sum[x][o << 1 | 1] ;min[x][o] = Min ( min[x][o << 1] , min[x][o << 1 | 1] ) ;max[x][o] = Max ( max[x][o << 1] , max[x][o << 1 | 1] ) ;
}void PushDown ( int x , int l , int r , int o ) {int m = ( l + r ) >> 1 ;if ( set[x][o] ) {int tmp = set[x][o] ;set[x][o << 1] = tmp ;min[x][o << 1] = tmp ;max[x][o << 1] = tmp ;sum[x][o << 1] = tmp * ( m - l + 1 ) ;add[x][o << 1] = 0 ;set[x][o << 1 | 1] = tmp ;min[x][o << 1 | 1] = tmp ;max[x][o << 1 | 1] = tmp ;sum[x][o << 1 | 1] = tmp * ( r - m ) ;add[x][o << 1 | 1] = 0 ;set[x][o] = 0 ;}if ( add[x][o] ) {int tmp = add[x][o] ;add[x][o << 1] += tmp ;min[x][o << 1] += tmp ;max[x][o << 1] += tmp ;sum[x][o << 1] += tmp * ( m - l + 1 ) ;add[x][o << 1 | 1] += tmp ;min[x][o << 1 | 1] += tmp ;max[x][o << 1 | 1] += tmp ;sum[x][o << 1 | 1] += tmp * ( r - m ) ;add[x][o] = 0 ;}
}void Build ( int x , int l , int r , int o ) {set[x][o] = add[x][o] = 0 ;if ( l == r ) {min[x][o] = max[x][o] = sum[x][o] = 0 ;return ;}int m = ( l + r ) >> 1 ;Build ( x , lson ) ;Build ( x , rson ) ;
}void Set ( int L , int R , int v , int x , int l , int r , int o ) {if ( L <= l && r <= R ) {add[x][o] = 0 ;set[x][o] = v ;min[x][o] = v ;max[x][o] = v ;sum[x][o] = v * ( r - l + 1 ) ;return ;}PushDown ( x , l , r , o ) ;int m = ( l + r ) >> 1 ;if ( L <= m ) Set ( L , R , v , x , lson ) ;if ( m < R ) Set ( L , R , v , x , rson ) ;PushUp ( x , o ) ;
}void Add ( int L , int R , int v , int x , int l , int r , int o ) {if ( L <= l && r <= R ) {add[x][o] += v ;min[x][o] += v ;max[x][o] += v ;sum[x][o] += v * ( r - l + 1 ) ;return ;}PushDown ( x , l , r , o ) ;int m = ( l + r ) >> 1 ;if ( L <= m ) Add ( L , R , v , x , lson ) ;if ( m < R ) Add ( L , R , v , x , rson ) ;PushUp ( x , o ) ;
}int ansmin , ansmax , anssum ;void Query ( int L , int R , int x , int l , int r , int o ) {if ( L <= l && r <= R ) {ansmin = Min ( ansmin , min[x][o] ) ;ansmax = Max ( ansmax , max[x][o] ) ;anssum += sum[x][o] ;return ;}PushDown ( x , l , r , o ) ;int m = ( l + r ) >> 1 ;if ( L <= m ) Query ( L , R , x , lson ) ;if ( m < R ) Query ( L , R , x , rson ) ;
}void work () {int n , m , q , ch , x1 , x2 , y1 , y2 , v ;while ( ~scanf ( "%d%d%d" , &n , &m , &q ) ) {for ( int i = 1 ; i <= n ; ++ i ) Build ( i , 1 , m , 1 ) ;while ( q -- ) {scanf ( "%d" , &ch ) ;if ( 1 == ch ) {scanf ( "%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &v ) ;for ( int i = x1 ; i <= x2 ; ++ i ) {Add ( y1 , y2 , v , i , 1 , m , 1 ) ;}}if ( 2 == ch ) {scanf ( "%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &v ) ;for ( int i = x1 ; i <= x2 ; ++ i ) {Set ( y1 , y2 , v , i , 1 , m , 1 ) ;}}if ( 3 == ch ) {scanf ( "%d%d%d%d" , &x1 , &y1 , &x2 , &y2 ) ;ansmin = oo ;ansmax = 0 ;anssum = 0 ;for ( int i = x1 ; i <= x2 ; ++ i ) {Query ( y1 , y2 , i , 1 , m , 1 ) ;}printf ( "%d %d %d\n" , anssum , ansmin , ansmax ) ;}}}
}int main () {work () ;return 0 ;
}
这篇关于UVa 11992 Fast Matrix Operations 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
