Ural 1470. UFOs

83 阅读 0 评论 55 点赞

我是靠谱客的博主落后音响，这篇文章主要介绍Ural 1470. UFOs，现在分享给大家，希望可以做个参考。

三维树状数组，之前没有碰到过树状数组的问题，直接撞三维上的表示很蛋疼。拖了几天了，有点想不下去。然后看了下题解，发现自己略白痴。。。

复制代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 100000000;
#define N 130
#define MIN(a,b) ((a)<(b)?(a):(b))
int c[N][N][N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x,int y,int z)
{
    int sum=0;
    int x0=x,y0=y,z0=z;
    while(x>0)
    {
        y=y0;
        while(y>0)
        {
            z=z0;
            while(z>0)
            {
                sum+=c[x][y][z];
                z-=lowbit(z);
            }
            y-=lowbit(y);
        }
        x-=lowbit(x);
    }
    return sum;
}
void add(int x,int y,int z,int d)
{
    int x0=x,y0=y,z0=z;
    while(x<=n)
    {
        y=y0;
        while(y<=n)
        {
            z=z0;
            while(z<=n)
            {
                c[x][y][z]+=d;
                z+=lowbit(z);
            }
            y+=lowbit(y);
        }
        x+=lowbit(x);
    }
}

int main()
{
    scanf("%d",&n);
    int m;
    int x,y,z,k,x1,y1,z1;
    while(scanf("%d",&m),m!=3)
    {
        if(m==1)
        {
            scanf("%d%d%d%d",&x,&y,&z,&k);
            add(x+1,y+1,z+1,k);
        }
        else if(m==2)
        {
            scanf("%d%d%d%d%d%d",&x,&y,&z,&x1,&y1,&z1);
            k=sum(x1+1,y1+1,z1+1)
                    - sum(x1+1,y1+1,z) - sum(x1+1,y,z1+1) - sum(x,y1+1,z1+1)
                    + sum(x,y,z1+1) + sum(x,y1+1,z) + sum(x1+1,y,z)
                    - sum(x,y,z);
            printf("%dn",k);
        }
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 100000000;
#define N 130
#define MIN(a,b) ((a)<(b)?(a):(b))
int c[N][N][N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x,int y,int z)
{
    int sum=0;
    int x0=x,y0=y,z0=z;
    while(x>0)
    {
        y=y0;
        while(y>0)
        {
            z=z0;
            while(z>0)
            {
                sum+=c[x][y][z];
                z-=lowbit(z);
            }
            y-=lowbit(y);
        }
        x-=lowbit(x);
    }
    return sum;
}
void add(int x,int y,int z,int d)
{
    int x0=x,y0=y,z0=z;
    while(x<=n)
    {
        y=y0;
        while(y<=n)
        {
            z=z0;
            while(z<=n)
            {
                c[x][y][z]+=d;
                z+=lowbit(z);
            }
            y+=lowbit(y);
        }
        x+=lowbit(x);
    }
}

int main()
{
    scanf("%d",&n);
    int m;
    int x,y,z,k,x1,y1,z1;
    while(scanf("%d",&m),m!=3)
    {
        if(m==1)
        {
            scanf("%d%d%d%d",&x,&y,&z,&k);
            add(x+1,y+1,z+1,k);
        }
        else if(m==2)
        {
            scanf("%d%d%d%d%d%d",&x,&y,&z,&x1,&y1,&z1);
            k=sum(x1+1,y1+1,z1+1)
                    - sum(x1+1,y1+1,z) - sum(x1+1,y,z1+1) - sum(x,y1+1,z1+1)
                    + sum(x,y,z1+1) + sum(x,y1+1,z) + sum(x1+1,y,z)
                    - sum(x,y,z);
            printf("%dn",k);
        }
    }

    return 0;
}