二维树状数组。
推出一维的后便很易想出二维解法了，单次更新/查询的时间复杂度升为O(lgN*lgN)，因此还是可以接受的。
久违的1A。。。
|
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 |
int s,c[1025][1025]; void add() { int i,j,x,y,yy,a; scanf("%d%d%d",&x,&y,&a); ++x; ++y; for(i=1;x<=s;i<<=1) { if(x&i) { for(j=1,yy=y;yy<=s;j<<=1) { if(yy&j) { c[x][yy]+=a; yy+=j; } } x+=i; } } } int val(int x,int y) { int i,j,k=0,yy; for(i=1;x;i<<=1) { if(x&i) { for(j=1,yy=y;yy;j<<=1) { if(yy&j) { k+=c[x][yy]; yy-=j; } } x-=i; } } return k; } void que() { int l,b,r,t; scanf("%d%d%d%d",&l,&b,&r,&t); printf("%d\n",val(r+1,t+1)-val(l,t+1)-val(r+1,b)+val(l,b)); } int main() { int i; while(~scanf("%*d%d",&s)) { memset(c,0,sizeof c); while(scanf("%d",&i)) { if(i==1) add(); else if(i==2) que(); else break; } } return 0; } |