HDU 1892(书架统计 二维树状数组)
题意是在二维平面上在一些位置上进行数据的增删改查操作，使用树状数组（了解树状数组点这里）
原来的树状数组在求区间和时是 sum( x, y ) = getsum( y ) - getsum( x - 1 )，
在这道题中是 sum( x1, y1, x2, y2 ) = getsum( x2,y2 ) - getsum( x1-1, y2 ) - getsum( x2, y1-1 ) + getsum( x1-1, y1-1 )
如图所示：
注意所给位置是从 0 开始算的，用树状数组时要从 1 开始算，也就是说要在所有的坐标上加 1 。还要注意书架上开始时每个位置都有一本书。
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int x,y,xx,yy,n,t,k,cnt,num,shelf[1020][1020]; 4 char ch; 5 int lowbit(int x) 6 { 7 return x & (-x); 8 } 9 int aa(int x,int y) 10 { 11 int sum = 0; 12 for(int i = x; i > 0; i -= lowbit(i)) 13 for(int j = y; j > 0; j -= lowbit(j)) 14 sum += shelf[i][j]; 15 return sum; 16 } 17 void update(int x,int y,int val) 18 { 19 for(int i = x; i <= 1010; i+=lowbit(i)) 20 for(int j = y; j <= 1010; j+=lowbit(j)) 21 shelf[i][j] += val; 22 } 23 void init() 24 { 25 memset(shelf,0,sizeof(shelf)); 26 for(int i = 1; i < 1010; ++i) 27 for(int j = 1; j < 1010; ++j) 28 update(i,j,1); 29 } 30 void s(int x,int y,int xx,int yy) 31 { 32 if(x>xx) 33 { 34 k = xx; 35 xx = x; 36 x = k; 37 } 38 if(y>yy) 39 { 40 k = yy; 41 yy = y; 42 y = k; 43 } 44 printf("%d ",aa(xx+1,yy+1)-aa(x,yy+1)-aa(xx+1,y)+aa(x,y)); 45 } 46 47 int get_s(int x,int y) 48 { 49 return aa(x,y) - aa(x-1,y) - aa(x,y-1) + aa(x-1,y-1); 50 } 51 void d(int x,int y,int n) 52 { 53 k = get_s(x+1,y+1); 54 n = n>k?k:n; 55 update(x+1,y+1,-n); 56 } 57 void m(int x,int y,int xx,int yy,int n) 58 { 59 k = get_s(x+1,y+1); 60 n = n>k?k:n; 61 update(x+1,y+1,-n); 62 update(xx+1,yy+1,n); 63 } 64 int main() 65 { 66 scanf("%d",&t); 67 for(cnt = 1; cnt <= t; ++cnt) 68 { 69 scanf("%d",&num); 70 printf("Case %d: ",cnt); 71 init(); 72 while(num--) 73 { 74 scanf("%c",&ch); 75 if(ch=='S') 76 { 77 scanf("%d%d%d%d",&x,&y,&xx,&yy); 78 s(x,y,xx,yy); 79 } 80 else if(ch=='A') 81 { 82 scanf("%d%d%d",&x,&y,&n); 83 update(x+1,y+1,n); 84 } 85 else if(ch=='D') 86 { 87 scanf("%d%d%d",&x,&y,&n); 88 d(x,y,n); 89 } 90 else if(ch=='M') 91 { 92 scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&n); 93 m(x,y,xx,yy,n); 94 } 95 else num++; 96 } 97 } 98 return 0; 99 }