UVA 11992-Fast Matrix Operations(線分ツリー+区間修正+好題)
14225 ワード
UVA 11992-Fast Matrix Operations(線分ツリー+区間修正+好題)
これは白い本の上の例題で、ずっと置いていてAに落ちていないで、これは1本の線分の木の区間の修正の良い問題です.
セグメントツリーでは、3つのドメイン、max、min、sum、すなわち区間最大値、最小値、区間と
テーマ:
r c 0 ，
1 x1 y1 x2 y2 v (x1,y1,x2,y2) v
2 x1 y1 x2 y2 v (x1,y1,x2,y2) v
3 x1 y1 x2 y2 (x1,y1,x2,y2) max,sum,min
0< c <=20 1< m <= 20000分析:
r 20， ，
。
3 x1 y1 x2 y2 ，
x1 - x2 query()，
sum ,max min 。
， add, set
setv addv。
。
，set ， set ， add ， ， 。
1： ， set， add
2：set addv ， add setv
/* ***********************************************
ID : whiteblock63
LANG : G++
PROG : Uva11992-Fast Matrix Operation
DATE : 2014-10-05 10:34:04
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define CLR( a, b ) memset( a, b, sizeof(a) )
#define ls o << 1
#define rs o << 1 | 1
#define rt l, r, o
#define lson l, m, o << 1
#define rson m + 1, r, o << 1 | 1
const int NODE_SIZE = 1 << 17;
const int INF = 0x3f3f3f3f;
int op, x1, x2, y1, y2, x, v;
//
inline void scan( int & x ){
char c;
while( c = getchar(), c < '0' || c > '9' );
x = c - '0';
while( c = getchar(), c >= '0' && c <= '9' ) x = x*10 + c - '0';
}
// struct SegTree{
int sumv[NODE_SIZE], minv[NODE_SIZE], maxv[NODE_SIZE];
int setv[NODE_SIZE], addv[NODE_SIZE];
void pushup( int l, int r, int o ){
if( l < r ){
sumv[o] = sumv[ls] + sumv[rs];
minv[o] = min( minv[ls], minv[rs] );
maxv[o] = max( maxv[ls], maxv[rs] );
}
if( setv[o] >= 0 ){
minv[o] = maxv[o] = setv[o];
sumv[o] = setv[o] * ( r - l + 1 );
}
if( addv[o] ){
minv[o] += addv[o];
maxv[o] += addv[o];
sumv[o] += addv[o] * ( r - l + 1 );
}
}
void pushdown( int o ){
if( setv[o] >= 0 ){
setv[ls] = setv[rs] = setv[o];
addv[ls] = addv[rs] = 0;
setv[o] = -1; //
}
if( addv[o] ){
addv[ls] += addv[o];
addv[rs] += addv[o];
addv[o] = 0; //
}
}
void update( int l, int r, int o ){
if( y1 <= l && r <= y2 ){
if( op == 1 ) addv[o] += v;
else setv[o] = v, addv[o] = 0;
}else{
pushdown( o );
int m = l + r >> 1;
if( y1 <= m ) update( lson );
else pushup( lson );
if( y2 > m ) update( rson );
else pushup( rson );
}
pushup( rt );
}
void query( int l, int r, int o, int& ssum, int& smin, int& smax ){
pushup( rt ); // pushdown if( y1 <= l && r <= y2 ){
ssum = sumv[o];
smin = minv[o];
smax = maxv[o];
}else{
pushdown( o );
int m = l + r >> 1;
int lsum = 0, lmin = INF, lmax = -INF;
int rsum = 0, rmin = INF, rmax = -INF;
if( y1 <= m ) query( lson, lsum, lmin, lmax );
else pushup( lson );
if( y2 > m ) query( rson, rsum, rmin, rmax );
else pushup( rson );
ssum = lsum + rsum;
smin = min( lmin, rmin );
smax = max( lmax, rmax );
}
}
};
const int MAXR = 20 + 5;
SegTree tree[MAXR];
int main()
{
int r, c, m;
while( ~scanf( "%d %d %d", &r, &c, &m ) ){
CLR( tree, 0 );
for( x = 1; x <= r; ++x ){
CLR( tree[x].setv, -1 );
tree[x].setv[1] = 0;
}
while( m-- ){
scan( op ); scan( x1 ); scan( y1 ); scan( x2 ); scan( y2 );
if( op < 3 ){
scan( v );
for( x = x1; x <= x2; ++x ) tree[x].update( 1, c, 1 );
}else{
int gsum = 0, gmin = INF, gmax = -INF;
for( x = x1; x <= x2; ++x ){
int ssum, smin, smax;
tree[x].query( 1, c, 1, ssum, smin, smax );
gsum += ssum;
gmin = min( gmin, smin );
gmax = max( gmax, smax );
}
printf("%d %d %d
", gsum, gmin, gmax );
}
}
}
return 0;
}