HDU 4456（二维树状数组+坐标转换）

题目链接：Problem - 4456

看别人叙述看的心烦，于是我自己画了一张图。

上图。

上代码

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn = ;

 const int maxm = 3e6+; //这里大小的确定应该是80000*log2(20000)*log2(20000),算出来大约是一千三百万，数据应该是水一些，然而看所有人的题解，都是四百万，呵呵呵，这其中一定有什么交易。

 int p[maxn],x[maxn],y[maxn],z[maxn];

 int arr[maxm];

 int cnt[maxm];

 int num = ;

 int len = ;

 int w = ;

 int lowbit(int x)

 {

     return x&(-x);

 }

 void pre(int x,int y)

 {

     for(int i=x;i<=w;i+=lowbit(i))

     {

         for(int j=y;j<=w;j+=lowbit(j))

         {

             cnt[num++] = i*w+j;

         }

     }

 }

 void sum(int x,int y,int tt)

 {

     for(int i=x;i<=w;i+=lowbit(i))

     {

         for(int j=y;j<=w;j+=lowbit(j))

         {

             int id = lower_bound(cnt,cnt+len,i*w+j)-cnt;

             arr[id] += tt;

         }

     }

 }

 int getsum(int x,int y)

 {

     x=max(x,); x=min(x,w); //边界

     y=max(y,); y=min(y,w);

     int summ = ;

     for(int i=x;i>;i-=lowbit(i))

     {

         for(int j=y;j>;j-=lowbit(j))

         {

             int id = lower_bound(cnt,cnt+len,i*w+j)-cnt;

             if(cnt[id]==(i*w+j)) summ += arr[id];

         }

     }

     return summ;

 }

 int main()

 {

     int n,m;

     while(scanf("%d",&n)!=EOF&&n)

     {

         scanf("%d",&m);

         w = *n;

         memset(cnt,,sizeof(cnt));

         memset(arr,,sizeof(arr));

         num = ;

         for(int i=;i<=m;i++)

         {

             scanf("%d %d %d %d",&p[i],&x[i],&y[i],&z[i]);

             int nx = x[i]-y[i]+n;

             int ny = x[i]+y[i];

             if(p[i]==)

             pre(nx,ny);

         }

         sort(cnt,cnt+num);

         len = unique(cnt,cnt+num)-cnt;

         for(int i=;i<=m;i++)

         {

             int nx = x[i]-y[i]+n;

             int ny = x[i]+y[i];

             if(p[i]==)

             {

                 sum(nx,ny,z[i]);

             }

             else

             {

                 int x1,y1,x2,y2,x3,y3,x4,y4;

                 x1 = nx+z[i];y1 = ny+z[i];

                 x2 = nx+z[i];y2 = ny-z[i];y2--;

                 x3 = nx-z[i];y3 = ny+z[i];x3--;

                 x4 = nx-z[i];y4 = ny-z[i];x4--;y4--;

                 printf("%d\n",getsum(x1,y1)-getsum(x2,y2)-getsum(x3,y3)+getsum(x4,y4));

             }

         }

     }

     return ;

 }