ural1470 UFOs-白红宇

ural1470 UFOs

阅读量：5051 次

发布时间：2019-06-12

本文共 3308 字，大约阅读时间需要 11 分钟。

UFOs

Time limit: 2.0 second

Memory limit: 64 MB

Vasya is a ufologist and his duties include observing Unidentified Flying Objects (UFOs) in the part of space bounded by a cube

N ×

N. The cube is divided into cubic sectors 1 × 1 × 1. During the observation, the following events may happen:

several new UFOs emerge in a certain sector;

several UFOs disappear in a certain sector;

Vasya's boss may ask him how many UFOs there are in a part of space consisting of several sectors.

At the moment when Vasya starts his observations there are no UFOs in the whole space.

Input

The first line contains an integer

N (1 ≤

N ≤ 128). The coordinates of sectors are integers from 0 to

N–1.

Then there are entries describing events, one entry per line. Each entry starts with a number

If M is 1, then this number is followed by four integers x (0 ≤ x < N), y (0 ≤ y < N), z (0 ≤ z < N), K (–20000 ≤ K ≤ 20000), which are coordinates of a sector and the change in the number of UFOs in this sector. The number of UFOs in a sector cannot become negative.

If M is 2, then this number is followed by six integers x1, y1, z1, x2, y2, z2 (0 ≤ x1 ≤ x2 <N, 0 ≤ y1 ≤ y2 < N, 0 ≤ z1 ≤ z2 < N), which mean that Vasya must compute the total number of UFOs in sectors (x, y, z) belonging to the volume: x1 ≤ x ≤ x2, y1 ≤ y ≤ y2, z1 ≤ z ≤z2.

If M is 3, it means that Vasya is tired and goes to sleep. This entry is always the last one.

The number of entries does not exceed 100002.

Output

For each query, output in a separate line the required number of UFOs.

Sample

input	output
22 1 1 1 1 1 11 0 0 0 11 0 1 0 32 0 0 0 0 0 02 0 0 0 0 1 01 0 1 0 -22 0 0 0 1 1 13	0142

input

output

22 1 1 1 1 1 11 0 0 0 11 0 1 0 32 0 0 0 0 0 02 0 0 0 0 1 01 0 1 0 -22 0 0 0 1 1 13

分析：三维树状数组，求和时类似于容斥；

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                    
                     ::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector
                     
                      #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair
                      
                       #define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e5+10;const int dis[4][2]={ { 0,1},{-1,0},{ 0,-1},{ 1,0}};using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t;ll a[129][129][129];void add(int x,int y,int z,int w){ for(int i=x;i<=n;i+=(i&(-i))) for(int j=y;j<=n;j+=(j&(-j))) for(int k=z;k<=n;k+=(k&(-k))) a[i][j][k]+=w;}ll get(int x,int y,int z){ ll ans=0; for(int i=x;i;i-=(i&(-i))) for(int j=y;j;j-=(j&(-j))) for(int k=z;k;k-=(k&(-k))) ans+=a[i][j][k]; return ans;}int main(){ int i,j; scanf("%d",&n); while(~scanf("%d",&m)&&m!=3) { if(m==1) { int b[4]; rep(i,0,3)scanf("%d",&b[i]); add(++b[0],++b[1],++b[2],b[3]); } else { int b[6]; rep(i,0,5)scanf("%d",&b[i]),b[i]++; printf("%lld\n",get(b[3],b[4],b[5]) -get(b[0]-1,b[4],b[5])-get(b[3],b[1]-1,b[5])-get(b[3],b[4],b[2]-1) +get(b[0]-1,b[1]-1,b[5])+get(b[3],b[1]-1,b[2]-1)+get(b[0]-1,b[4],b[2]-1) -get(b[0]-1,b[1]-1,b[2]-1)); } } //system("Pause"); return 0;}