首页 > 代码库 > G - UFOs

G - UFOs

2024-07-15 08:27:37   220人阅读

Description

Vasya is a ufologist and his duties include observing Unidentified Flying Objects (UFOs) in the part of space bounded by a cube N × 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 M.
  • 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

inputoutput
2
2 1 1 1 1 1 1
1 0 0 0 1
1 0 1 0 3
2 0 0 0 0 0 0
2 0 0 0 0 1 0
1 0 1 0 -2
2 0 0 0 1 1 1
3

0
1
4
2
题目大意：

描述：Vasya 不明飞行物研究家，他的职责是观察UFO在一个N × N ×N的空间里的存在情况，这个空间被分成1 × 1 × 1的小区域，在这些小区域中会发生下列事件：

                    一些小区域会出现一些新的UFO；

                    一些UFO会在一些小区域消失；

                    Vasya 的上司会询问他某个区域的UFO有多少；

当Vasya开始观察UFO时，在整个区域内没有UFO。

输入：

第一行包含一个整数N(1 ≤ N ≤ 128).。区域的坐标是从0到N-1。

然后又多行描述，每行的第一个数是M。

             如果M是1，接着就有四个整数，分别为 x (0 ≤ x < N), y (0 ≤ y < N), z (0 ≤ z < N), K (–20000 ≤ K ≤ 20000)，x，y，z表示UFO出现的小区域，K表示UFO出现的数量。

             如果M是2，接着就有六个整数 x1, y1, z1, x2, y2, z2 (0 ≤ x1 ≤ x2 < N, 0 ≤ y1 ≤ y2 < N, 0 ≤ z1 ≤ z2 < N)，（x1，y1，z1）与（x2，y2，z2）分别表示所求区域的体对角线上的点。

              如果M是3，那么Vasya就可以结束任务，回家睡觉了。

输出：

对Vasya上司的每句询问，都输出当前该区域UFO的数量，并且结果占一行。


本题可以利用三维树状数组，其实和一维树状数组，二维树状数组差不多，只是在更新（update）函数和求和（SUM）函数中相对一维、二维树状数组多了两、一个for循环而已，在最后的调用SUM函数是稍复杂些罢了。

代码如下：

//三维树状数组
#include<stdio.h>
#include<string.h>
#define max 130
int N;
//三维树状数组（s[ ][ ][ ]）用来储存出现UFO的数量，由于数量值较大，采用long long型
long long s[max][max][max]={0};
int lowbit(int x)
{
    return x&(-x);
}
//更新函数，对树状数组某一元素（x，y，z）加减某一num值
void update(int x,int y,int z,int num)
{
    int i,j,k;
    for(i=x;i<=N;i+=lowbit(i))
    {
        for(j=y;j<=N;j+=lowbit(j))
        {
            for(k=z;k<=N;k+=lowbit(k))
                s[i][j][k]+=num;
        }
    }
}
//求和函数，对树状数组某区域内的元素求和，注意数值较大，采用long long型
long long SUM(int x,int y,int z)
{
    int i,j,k;
    long long ans=0;
    for(i=x;i>0;i-=lowbit(i))
    {
        for(j=y;j>0;j-=lowbit(j))
        {
            for(k=z;k>0;k-=lowbit(k))
                ans+=s[i][j][k];
        }
    }
    return ans;
}
int main()
{
    long long sum;
    int x,y,z,x1,x2,y1,y2,z1,z2,M,K;
    scanf("%d",&N);
    while(scanf("%d",&M)&&M!=3)
    {
        if(M==1)
        {
            //输入要更新的元素以及更新的值
            scanf("%d%d%d%d",&x,&y,&z,&K);
            /*对相应元素更新，注意树状数组是
            从1开始储存的，输入的元素是从0开始的*/
            update(x+1,y+1,z+1,K);
        }
        if(M==2)
        {
            //输入需要求和的区域
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
            //求和
            sum=SUM(x2+1,y2+1,z2+1)-SUM(x2+1,y2+1,z1)-SUM(x2+1,y1,z2+1)-SUM(x1,y2+1,z2+1)+SUM(x1,y1,z2+1)+SUM(x1,y2+1,z1)+SUM(x2+1,y1,z1)-SUM(x1,y1,z1);
            printf("%lld\n",sum);
        }
    }
    return 0;
}







联系
我们