Main idea is to split cube into 8 parts and query/add for each one.
Here is my code that have TL6.
Any ideas of how to improve it?

import java.io.*;

public class P1470 {
    static int [] tree = new int[10000000];
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

        n = Integer.valueOf(reader.readLine());

        while (true) {
            String line = reader.readLine();
            if (line.startsWith("1")) {
                add(new Ufo(line));
            } else if (line.startsWith("2")){
                writer.println(query(new Region(line)));
            } else {
                break;
            }
        }
        writer.flush();
    }

    private static int query(Region region) {
        return doQuery(region, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static int doQuery(Region q, Region r, int node) {
        if (!r.overlaps(q)) return 0;
        if (q.contains(r)) {
            return tree[node];
        }
        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        return
            doQuery(q, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1) +
            doQuery(q, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2) +
            doQuery(q, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3) +
            doQuery(q, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4) +
            doQuery(q, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5) +
            doQuery(q, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6) +
            doQuery(q, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7) +
            doQuery(q, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    private static void add(Ufo ufo) {
        doAdd(ufo, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static void doAdd(Ufo ufo, Region r, int node) {
        if (!r.contains(ufo)) return;

        tree[node] += ufo.count;

        if (r.isPoint()) return;

        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        doAdd(ufo, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1);
        doAdd(ufo, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2);
        doAdd(ufo, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3);
        doAdd(ufo, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4);
        doAdd(ufo, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7);
        doAdd(ufo, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    static class Region {
        int x1, y1, z1, x2, y2, z2;

        Region(String s) {
            String[] split = s.split("\\s");
            x1 = Integer.valueOf(split[1]);
            y1 = Integer.valueOf(split[2]);
            z1 = Integer.valueOf(split[3]);
            x2 = Integer.valueOf(split[4]);
            y2 = Integer.valueOf(split[5]);
            z2 = Integer.valueOf(split[6]);
        }

        Region(int x1, int y1, int z1, int x2, int y2, int z2) {
            this.x1 = x1;
            this.y1 = y1;
            this.z1 = z1;
            this.x2 = x2;
            this.y2 = y2;
            this.z2 = z2;
        }

        boolean contains(Ufo ufo) {
            return ufo.x >= x1 && ufo.x <= x2 && ufo.y >= y1 && ufo.y <= y2 && ufo.z >= z1 && ufo.z <= z2;
        }

        boolean contains(Region r) {
            return overlaps(r) && x1 <= r.x1 && x2 >= r.x2 && y1 <= r.y1 && y2 >= r.y2 && z1 <= r.z1 && z2 >= r.z2;
        }

        boolean overlaps(Region r) {
            return r.x1 <= x2 && r.x2 >= x1 && r.y1 <= y2 && r.y2 >= y1 && r.z1 <= z2 && r.z2 >= z1;
        }

        boolean isPoint() {
            return x1 == x2 && y1 == y2 && z1 == z2;
        }
    }

    static class Ufo {
        int x, y, z, count;

        Ufo(String s) {
            String[] split = s.split("\\s");
            x = Integer.valueOf(split[1]);
            y = Integer.valueOf(split[2]);
            z = Integer.valueOf(split[3]);
            count = Integer.valueOf(split[4]);
        }
    }
}

I used template programming to write 3D Fenwick tree and I get "Compiler failed" verdict when compiling with G++ (not "Compilation Error", but "Compiler failed"; no error message). The solution works fine and gets Accepted with Visual Studio and Clang.

I assume it is because of the recursive template operations, but it works when I compile it locally with G++ (using the flags provided on help.aspx?topic=cpp). It also work on other online judges, such as codeforces, which also use mingw g++.

Could I get some insight on this? I'm curious why this happens.

Just write 3d Fenvick Tree. And nothing more.

Who can give test 2. In some topic was given some and my programm gives right result.

What is test 4?

why my progam get it???
I think its correct
z wrote many tests and all of them my program pass corectly
but in test 2 some strange...
I know that N in 2 test = 2
if it test from statement?
please give me some tests like test #2

here is my code(Fenvick Tree 3D)

//code deleted

some tests for WA2
3
1 1 1 0 2
1 0 0 0 3
1 0 0 1 3
2 1 1 0 2 2 2
3
answer 2
2
1 0 0 0 10
1 0 0 1 10000
1 0 1 0 50
1 0 1 1 1000
1 1 0 0 5
1 1 0 1 100
1 1 1 0 1
1 1 1 1 127
2 1 1 1 1 1 1
3
answer 127
this tests useful for fenvick tree solution!

Edited by author 22.04.2009 20:19

жаль, но октодерево не проходит по времени. В данной задаче сложность запроса на получения количества НЛО в области - O(N*N)

my  simple algo don't fit
if compute on each step number of UFO wich
belong to sector - its too long (O(n*n))
What's the correct algo for this task?

Look at this test
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
In 6 line we have m=2 but z1>z2. Why???

It has built on my computer successfully.
The code is shown below. Help me!

---
The code has hidden. Thank you.

Hint:
Function xxxx(***):***;
You'd better not do anything with the result variable before you exit the function.
---

Edited by author 26.09.2006 08:09