首页 > 代码库 > HDU_4456_二维树状数组
HDU_4456_二维树状数组
http://acm.hdu.edu.cn/showproblem.php?pid=4456
第一道二维树状数组就这么麻烦,题目要计算的是一个菱形范围内的和,于是可以把原来的坐标系旋转45度,就是求一个正方形范围内的和,这里还涉及到坐标系平移和放大,由于题目数据较大,用了离散化来保存需要处理的点,放在h数组内,对应的二维树状数组存在tree数组内。
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;inline int lowbit(int x){ return x & (-x);}int p[80050],posx[80050],posy[80050],v[80050],h[4500000],tree[4500000],n,m,N,cnt;void update(int x,int y,int z){ for(int i = x;i <= N;i += lowbit(i)) { for(int j = y;j <= N;j += lowbit(j)) { int pos = lower_bound(h,h+cnt,i*N+j)-h; tree[pos] += z; } }}int getsum(int x,int y){ int ans = 0; for(int i = x;i > 0;i -= lowbit(i)) { for(int j = y;j > 0;j -= lowbit(j)) { int pos = lower_bound(h,h+cnt,i*N+j)-h; if(h[pos] == i*N+j) ans += tree[pos]; } } return ans;}int main(){ while(scanf("%d",&n) && n) { memset(tree,0,sizeof(tree)); int x,y; N = 2*n; cnt = 0; scanf("%d",&m); for(int i = 1;i <= m;i++) { scanf("%d%d%d%d",&p[i],&x,&y,&v[i]); int xx = x-y+n,yy = x+y; posx[i] = xx; posy[i] = yy; if(p[i] == 1) { for(int j = xx;j <= N;j += lowbit(j)) { for(int k = yy;k <= N;k += lowbit(k)) { h[cnt++] = j*N+k; } } } } sort(h,h+cnt); for(int i = 1;i <= m;i++) { if(p[i] == 1) update(posx[i],posy[i],v[i]); else { int x1 = max(1,posx[i]-v[i]),y1 = max(1,posy[i]-v[i]); int x2 = min(N,posx[i]+v[i]),y2 = min(N,posy[i]+v[i]); printf("%d\n",getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1)); } } } return 0;}
HDU_4456_二维树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。