Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个代码。第一次写树状数组,ac#include<iostream> #include<stdio.h> using namespace std; int a[1026][1026]; int lowbit(int x) { return x&(-x); } void add(int x,int y,int n,int val) { for(int i=x;i<=n;i+=lowbit(i)) { for(int j=y;j<=n;j+=lowbit(j)) { a[i][j]+=val; } } } int sum(int x,int y) { int res=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) res+=a[i][j]; return res; } int main() { int cas,n; while(scanf("%d",&cas)) { if(cas==3) break; if(cas==0) { scanf("%d",&n); memset(a,0,sizeof(a)); } if(cas==1) { int x,y,t; scanf("%d %d %d",&x,&y,&t); add(x+1,y+1,n,t); } if(cas==2) { int x1,x2,y1,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); printf("%d\n",sum(x2+1,y2+1)+sum(x1,y1)-sum(x1,y2+1)-sum(x2+1,y1)); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator