本文主要是介绍【UVALive】6709 Mosaic 二维线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【UVALive】6709 Mosaic题目大意：
每次选择矩阵中的一个点，求以他为中心，边长为D（D一定是奇数）的矩阵中的最小值min和最大值max，输出ans =（min+max）/ 2（向下取整）。然后将该点的值修改为ans。
题目分析：
赤果果的二维线段树单点修改、区间查询。
又一次学习了线段树，发现原来所有的更新操作全部放在二维中即可。
很不错，一定要经常看看，温故知新~
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long BigInt ;#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt o , l , r
#define root 1 , 1 , n
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define LLRR Lx , Rx , Ly , Ry
#define clear( A , X ) memset ( A , X , sizeof A )const int maxN = 800 ;
const int oo = 0x3f3f3f3f ;int mmax[maxN << 2][maxN << 2] ;
int mmin[maxN << 2][maxN << 2] ;
int minv , maxv ;
int n ;int max ( const int a , const int b ) {if ( a > b ) return a ;return b ;
}int min ( const int a , const int b ) {if ( a < b ) return a ;return b ;
}void PushUp ( int pos , int o ) {mmax[pos][o] = max ( mmax[pos][ls] , mmax[pos][rs] ) ;mmin[pos][o] = min ( mmin[pos][ls] , mmin[pos][rs] ) ;
}void SubBuild ( int ch , int pos , int o , int l , int r ) {mmax[pos][o] = -oo ;mmin[pos][o] = oo ;if ( l == r ) {if ( !ch ) { scanf ( "%d" , &mmin[pos][o] ) ;mmax[pos][o] = mmin[pos][o] ;}else {mmin[pos][o] = min ( mmin[pos << 1][o] , mmin[pos << 1 | 1][o] ) ;mmax[pos][o] = max ( mmax[pos << 1][o] , mmax[pos << 1 | 1][o] ) ;}return ;}int m = mid ;SubBuild ( ch , pos , lson ) ;SubBuild ( ch , pos , rson ) ;PushUp ( pos , o ) ;
}void Build ( int o , int l , int r ) {if ( l == r ) {SubBuild ( 0 , o , root ) ;return ;}int m = mid ;Build ( lson ) ;Build ( rson ) ;SubBuild ( 1 , o , root ) ;
}void SubUpdate ( int ch , int pos , int y , int v , int o , int l , int r ) {if ( l == r ) {if ( !ch ) mmin[pos][o] = mmax[pos][o] = v ;else {mmin[pos][o] = min ( mmin[pos << 1][o] , mmin[pos << 1 | 1][o] ) ;mmax[pos][o] = max ( mmax[pos << 1][o] , mmax[pos << 1 | 1][o] ) ;}return ;}int m = mid ;if ( y <= m ) SubUpdate ( ch , pos , y , v , lson ) ;else SubUpdate ( ch , pos , y , v , rson ) ;PushUp ( pos , o ) ;
}void Update ( int x , int y , int v , int o , int l , int r ) {if ( l == r ) {SubUpdate ( 0 , o , y , v , root ) ;return ;}int m = mid ;if ( x <= m ) Update ( x , y , v , lson ) ;else Update ( x , y , v , rson ) ;SubUpdate ( 1 , o , y , v , root ) ;
}void SubQuery ( int L , int R , int pos , int o , int l , int r ) {if ( L <= l && r <= R ) {minv = min ( minv , mmin[pos][o] ) ;maxv = max ( maxv , mmax[pos][o] ) ;return ;}int m = mid ;if ( L <= m ) SubQuery ( L , R , pos , lson ) ;if ( m < R ) SubQuery ( L , R , pos , rson ) ;
}void Query ( int Lx , int Rx , int Ly , int Ry , int o , int l , int r ) {if ( Lx <= l && r <= Rx ) {SubQuery ( Ly , Ry , o , root ) ;return ;}int m = mid ;if ( Lx <= m ) Query ( LLRR , lson ) ;if ( m < Rx ) Query ( LLRR , rson ) ;
}void work () {int m , w , x , y ;int x1 , x2 , y1 , y2 ;scanf ( "%d" , &n ) ;Build ( root ) ;scanf ( "%d" , &m ) ;while ( m -- ) {scanf ( "%d%d%d" , &x , &y , &w ) ;w >>= 1 ;x1 = max ( 1 , x - w ) ;x2 = min ( n , x + w ) ;y1 = max ( 1 , y - w ) ;y2 = min ( n , y + w ) ;minv = oo , maxv = -oo ;Query ( x1 , x2 , y1 , y2 , root ) ;int v = ( minv + maxv ) >> 1 ;printf ( "%d\n" , v ) ;Update ( x , y , v , root ) ;}
}int main () {int T , cas ;for ( scanf ( "%d" , &T ) , cas = 1 ; cas <= T ; ++ cas ) {printf ( "Case #%d:\n" , cas ) ;work () ;}return 0 ;
}这篇关于【UVALive】6709 Mosaic 二维线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
