1470. UFOs(三维树状数组）

时间：2021-03-20 09:18:16

1470

最简单的三维树状数组

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define lowbit(x) x&(-x)

 int re[][][],n;

 int getsum(int x,int y,int z)

 {

     int s = ,i,j,g;

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

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

             for(g = z ; g >=  ; g-=lowbit(g))

                 s+=re[i][j][g];

     return s;

 }

 void add(int x,int y,int z,int da)

 {

     int i,j,g;

     for(i = x ; i <= n ; i+=lowbit(i))

         for(j = y ; j <= n ; j+=lowbit(j))

            for(g = z ; g <= n ; g+=lowbit(g))

                 re[i][j][g]+=da;

 }

 int main()

 {

     int k,x1,x2,x3,x4,x5,x6,p;

     scanf("%d",&n);

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

     {

         if(k==)

         break;

         if(k==)

         {

             scanf("%d%d%d%d",&x1,&x2,&x3,&p);

             add(x1+,x2+,x3+,p);

         }

         else

         {

             scanf("%d%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5,&x6);

             x4+=,x5+=,x6+=;

             int ans = ;

             ans+=getsum(x4,x5,x6);

             ans-=getsum(x1,x5,x6);

             ans-=getsum(x4,x2,x6);

             ans-=getsum(x4,x5,x3);

             ans+=getsum(x1,x5,x3);

             ans+=getsum(x4,x2,x3);

             ans+=getsum(x1,x2,x6);

             ans-=getsum(x1,x2,x3);

             printf("%d\n",ans);

         }

     }

     return ;

 }

相关文章