The QianJin Teaching Building - nazgul's Blog
The QianJin Teaching Building
nazgul
posted @ 2010年10月18日 23:46
in HNU
, 930 阅读
http://acm.hnu.cn/online/?action=problem&type=show&id=11444
二维树状数组支持两种操作,一种修改二维数组中任意元素的值,另一种是查询任意范围的元素和.
题目中的4种操作都可以用以上两种操作完成.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include <stdio.h>#include <string.h>#define maxn 1002int c[maxn][maxn];int lowbit( int x ){ return x & ( -x );}int sum( int x, int y ){ int i, j, t=0; for ( i=x; i>0; i-=lowbit(i) ) for ( j=y; j>0; j-=lowbit(j) ) t += c[i][j]; return t;}void Insert( int x, int y, int a ){ int i, j; for ( i=x; i<maxn; i+=lowbit(i) ) for ( j=y; j<maxn; j+=lowbit(j) ) c[i][j] += a;}int Query( int x1, int y1, int x2, int y2 ){ return sum( x2, y2 )-sum( x1-1, y2 )-sum( x2, y1-1 )+sum( x1-1, y1-1 );}int main(){ int cases, T, m, x1, y1, x2, y2, v, t; char s[2]; //freopen( "//home//administrator//32.in", "r", stdin ); //freopen( "//home//administrator//test.out", "w", stdout ); scanf( "%d", &cases ); for ( T=1; T<=cases; ++T ) { printf( "Case %d:\n", T ); memset( c, 0, sizeof( c ) ); scanf( "%d", &m ); while ( m-- ) { scanf( "%s", s ); if ( s[0] == 'A' ) { scanf( "%d%d%d", &x1, &y1, &v ); x1++; y1++; Insert( x1, y1, v ); } else if ( s[0] == 'D' ) { scanf( "%d%d%d", &x1, &y1, &v ); x1++; y1++; t = Query( x1, y1, x1, y1 )+1; if ( v > t ) v = t; Insert( x1, y1, -v ); } else if ( s[0] == 'M' ) { scanf( "%d%d%d%d%d", &x1, &y1, &x2, &y2, &v ); x1++; y1++; x2++; y2++; t = Query( x1, y1, x1, y1 )+1; if ( v > t ) v = t; Insert( x1, y1, -v ); Insert( x2, y2, v ); } else if ( s[0] == 'S' ) { scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 ); x1++; y1++; x2++; y2++; if ( x1 > x2 ) { v = x1; x1 = x2; x2 = v; } if ( y1 > y2 ) { v = y1; y1 = y2; y2 = v; } v = Query( x1, y1, x2, y2 )+( x2-x1+1 )*( y2-y1+1 ); printf( "%d\n", v ); } } } return 0;} |
评论 (0)