首页 > 代码库 > 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_二维树状数组