POJ 1195 Mobile phones (二维树状数组)
1 X Y A 是在(X,Y)这个点加A
2 X1 Y1 X2 Y2 查询(X1,X2) 到 (Y1,Y2) 这个矩形范围内手机的数量
而且数据的边界也是从0开始用树状数组的时候要加一处理
对于求矩形面积用一个大的矩形剪去三个边界的小矩形即可
ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
//4352K 547MS #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define M 1050 int tree[M][M],lim; int lowbit(int x) { return x&-x; } void add(int x,int y,int val) { int tmp; while(x<=lim){ tmp=y; while(tmp<=lim){ tree[x][tmp]+=val; tmp+=lowbit(tmp); } x+=lowbit(x); } } int query(int x,int y) { int s=0; while(x>0){ int tmp=y; while(tmp>0){ s+=tree[x][tmp]; tmp-=lowbit(tmp); } x-=lowbit(x); } return s; } int main() { int op; while(scanf("%d",&op)&&op!=3){ if(op==0){ scanf("%d",&lim); lim++; } if(op==1){ int a,b,val; scanf("%d%d%d",&a,&b,&val); add(a+1,b+1,val); } if(op==2){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++; y1++; x2++; y2++; int ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1); printf("%d\n",ans); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。