hdu 1890 二维树状数组
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int sum[1010][1010]; int mark[1010][1010]; int add(int a,int b,int c) { int i,j; for(i=a;i<=1001;i+=(i&-i)) for(j=b;j<=1001;j+=(j&-j)) sum[i][j]+=c; return 0; } int find(int a,int b) { int i,j,s=0; for(i=a;i>0;i-=(i&-i)) for(j=b;j>0;j-=(j&-j)) s+=sum[i][j]; return s; } int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } int main() { int i,j,T,Q; int a1,a2,b1,b2,n,d=1; char str[5]; scanf("%d",&T); while(T--) { scanf("%d",&Q); printf("Case %d:\n",d++); memset(sum,0,sizeof(sum)); for(i=1;i<=1001;i++) for(j=1;j<=1001;j++) { mark[i][j]=1; add(i,j,1); } while(Q--) { scanf("%s",str); if(str[0]==‘S‘) { scanf("%d%d%d%d",&a1,&b1,&a2,&b2); a1++;a2++;b1++;b2++; int k1=max(a1,a2); int k2=min(a1,a2); int t1=max(b1,b2); int t2=min(b1,b2); int s1=find(k1,t1); int s2=find(k1,t2-1); int s3=find(k2-1,t1); int s4=find(k2-1,t2-1); printf("%d\n",s1-s2-s3+s4); } else if(str[0]==‘A‘) { scanf("%d%d%d",&a1,&b1,&n); a1++;b1++; add(a1,b1,n); mark[a1][b1]+=n; } else if(str[0]==‘D‘) { scanf("%d%d%d",&a1,&b1,&n); a1++;b1++; int step=mark[a1][b1]>n?n:mark[a1][b1]; add(a1,b1,-step); mark[a1][b1]-=step; } else { scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&n); a1++;a2++;b1++;b2++; int step=mark[a1][b1]>n?n:mark[a1][b1]; add(a1,b1,-step); add(a2,b2,step); mark[a1][b1]-=step; mark[a2][b2]+=step; } } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。