ACM数据结构部分模版.docxVIP

数据结构： 增加栈 #pragma comment(linker,/STACK:1024000000,1024000000) 二维树状数组 #includecstdio #includeiostream #includecstring #define maxn 130 using namespace std ; int xt[maxn][maxn][maxn] ; int add , z , n ; int low( int x ) { return x (-x) ; } // 二维树状数组，第三维枚举 void up( int x , int y ) { int i , j ; for( i = x ; i = maxn ;i+= low(i)) for( j = y ; j = maxn ; j+=low(j)) { xt[z][i][j] += add ; if( xt[z][i][j] 0 ) xt[z][i][j] = 0 ; } } int sum( int x , int y ) { int i ,ans = 0 ; for( i = x ;i 0 ;i -= low(i) ) for( int j = y ; j 0 ;j -= low(j) ) { ans += xt[z][i][j] ; } return ans ; } int main() { int x , y , a ; int x1 , y1 , z1 , z2 ; int x2 , y2 , ans ; while( cin n ) { memset( xt , 0 , sizeof(xt)) ; while( scanf( %d , a ) a != 3 ) { ans = 0 ; if( a == 1 ) { scanf( %d%d%d%d , x , y , z , add ) ; x+=2 ; y+=2 ; z+=2 ; up( x , y ) ; } else if( a == 2) { scanf( %d%d%d , x1 , y1 , z1 ) ; scanf( %d%d%d , x2 , y2 , z2 ) ; // 树状数组必须大于0，而且是整数 x1+=2;x2+=2;y1+=2;y2+=2;z1+=2;z2+=2; for( z = z1 ; z = z2 ;z++ ) { //求矩阵（x1,y1）(x2,y2) （对角）的和 公式 // sum(x2,y2) - sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) ans+=( sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) ); } printf(%d\n,ans); } } 线段树成段更新 void down( int o ,int L ,int R ) { if(add[o] != 0 ) { sum[o] += add[o]*(R-L+1) ; } } void update( int L ,int R ,int o ) { if( L = ql qr = R ) { add[o] += v ; sum[o] += v*(R-L+1) ; return ; } int mid = (L+R)1 ; if( ql = mid ) update(L,mid,o1) ; if(qr mid ) update(mid+1,R,o1|1) ; sum[o] = sum[o1]+sum[o1|1] ; down(o,L,R) ; } void find( int L ,int R ,int o ,LL _add ) { if( L = ql qr = R ) { v += sum[o] ; v += _add*(R-L+1) ; return ; } int mid = (L+R)1 ; if( ql = mid ) find(L,mid,o1,_add+add[o]) ; if(qr mid ) find(mid+1,R,o1|1,_add+add[o]) ; } void push( in