学步园

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 | 1

const 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 ;
}