You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries.
UPDATE x y z W
updates the value of block (x,y,z) to W.
QUERY x1 y1 z1 x2 y2 z2
calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive).
Input Format
The first line contains an integer T, the number of test-cases. T testcases follow.
For each test case, the first line will contain two integers N and M separated by a single space.
N defines the N * N * N matrix.
M defines the number of operations.
The next M lines will contain either
The first line contains an integer T, the number of test-cases. T testcases follow.
For each test case, the first line will contain two integers N and M separated by a single space.
N defines the N * N * N matrix.
M defines the number of operations.
The next M lines will contain either
1. UPDATE x y z W
2. QUERY x1 y1 z1 x2 y2 z2
Output Format
Print the result for each QUERY.
Print the result for each QUERY.
Constrains
1 <= T <= 50
1 <= N <= 100
1 <= M <= 1000
1 <= x1 <= x2 <= N
1 <= y1 <= y2 <= N
1 <= z1 <= z2 <= N
1 <= x,y,z <= N
-109 <= W <= 109
1 <= T <= 50
1 <= N <= 100
1 <= M <= 1000
1 <= x1 <= x2 <= N
1 <= y1 <= y2 <= N
1 <= z1 <= z2 <= N
1 <= x,y,z <= N
-109 <= W <= 109
Sample Input
2
4 5
UPDATE 2 2 2 4
QUERY 1 1 1 3 3 3
UPDATE 1 1 1 23
QUERY 2 2 2 4 4 4
QUERY 1 1 1 3 3 3
2 4
UPDATE 2 2 2 1
QUERY 1 1 1 1 1 1
QUERY 1 1 1 2 2 2
QUERY 2 2 2 2 2 2
Sample Output
4
4
27
0
1
1
Explanation
First test case, we are given a cube of 4 * 4 * 4 and 5 queries. Initially all the cells (1,1,1) to (4,4,4) are 0.
First test case, we are given a cube of 4 * 4 * 4 and 5 queries. Initially all the cells (1,1,1) to (4,4,4) are 0.
UPDATE 2 2 2 4 makes the cell (2,2,2) = 4 QUERY 1 1 1 3 3 3. As (2,2,2) is updated to 4 and the rest are all 0. The answer to this query is 4. UPDATE 1 1 1 23. updates the cell (1,1,1) to 23. QUERY 2 2 2 4 4 4. Only the cell (1,1,1) and (2,2,2) are non-zero and (1,1,1) is not between (2,2,2) and (4,4,4). So, the answer is 4. QUERY 1 1 1 3 3 3. 2 cells are non-zero and their sum is 23+4 = 27.
--------------------------------------------------------------------------------------------------
Cube Summation - - Hacker Rank Solution
This problem is based on fenwick trees. Consider this problem:
A High level explanation of fenwick tree.
Consider this problem:
Given an array(let say A) of size n initialized to zero. In this array only two operations can be performed
- update x
- summation i j
using fenwick tree both of these operation be done in O(logn) time.
First we have to construct a new array(let say B). B[i] stores summation of values of A[x] to A[i](here x is some index less than i). Now to get "summation x y" we have to calculate A[0]+....+A[j] and A[0]+....+A[i].
To get A[0]+....+A[j] we will make use of array B.
sum = 0;
while(j>0) {
sum += B[j];
j -= (j & -j); // consider updated j as x in above explanation.
}
This while loops takes O(logn) time. Similarly we can perform update operation.
In original problem we have to find summation in 3-dimensions. So we can again use fenwick tree with three dimension. Now summation operation will look like this:
long long y1,x1,sum=0;
while (z>0) {
x1=x;
while(x1>0) {
y1=y;
while(y1>0) {
sum += matrix[x1][y1][z];
y1-= (y1 & -y1);
}
x1 -= (x1 & -x1);
}
z -= (z & -z);
}
return sum;
Now Time Complexity of update and summation operation will be O((logn)^3). Since we have to reduce each x,y,z coordinate.
Problem Setter's code :
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long matrix[101][101][101];
void update(long long n,long long x,long long y,long long z,long long val) {
long long y1,x1;
while(z <= n) {
x1 = x;
while(x1 <= n) {
y1 = y;
while(y1 <= n) {
matrix[x1][y1][z] += val;
y1 += (y1 & -y1 );
}
x1 += (x1 & -x1);
}
z += (z & -z);
}
}
long long calculate_sum(long long x,long long y,long long z) {
long long y1,x1,sum=0;
while (z>0) {
x1=x;
while(x1>0) {
y1=y;
while(y1>0) {
sum += matrix[x1][y1][z];
y1-= (y1 & -y1);
}
x1 -= (x1 & -x1);
}
z -= (z & -z);
}
return sum;
}
void process(long long n,long long m) {
long long x,y,z,x0,y0,z0;
long long value1,value2,val;
char command[10];
memset(matrix,0,sizeof(matrix));
while(m--) {
scanf("%s",command);
if(!strcmp(command,"QUERY")) {
scanf("%lld %lld %lld %lld %lld %lld",&x0,&y0,&z0,&x,&y,&z);
value1 = calculate_sum(x,y,z)- calculate_sum(x0-1,y,z)
- calculate_sum(x,y0-1,z) + calculate_sum(x0-1,y0-1,z);
value2 = calculate_sum(x,y,z0-1) - calculate_sum(x0-1,y,z0-1)
- calculate_sum(x,y0-1,z0-1) + calculate_sum(x0-1,y0-1,z0-1);
printf("%lld\n",value1 - value2);
//PrintMatrix(n);
}
if(!strcmp(command,"UPDATE")) {
scanf("%lld %lld %lld %lld",&x,&y,&z,&val);
x0 = x;
y0 = y;
z0 = z ;
value1 = calculate_sum(x,y,z)- calculate_sum(x0-1,y,z)
- calculate_sum(x,y0-1,z) + calculate_sum(x0-1,y0-1,z);
value2 = calculate_sum(x,y,z0-1) - calculate_sum(x0-1,y,z0-1)
- calculate_sum(x,y0-1,z0-1) + calculate_sum(x0-1,y0-1,z0-1);
update(n,x,y,z,val -(value1 - value2 ));
}
}
}
int main() {
long long cases; scanf("%lld",&cases);
while(cases--) {
long long n,m; scanf("%lld %lld",&n,&m);
process(n,m);
}
return 0;
}
Problem Tester's code :
#include <bits/stdc++.h>
using namespace std;
const int sz = 111;
long long tree[sz][sz][sz];
void update(int x, int y, int z, long long val) {
int xx = x;
while(xx < sz) {
int yy = y;
while(yy < sz) {
int zz = z;
while(zz < sz) {
tree[xx][yy][zz] += val;
zz += zz & (-zz);
}
yy += yy & (-yy);
}
xx += xx&(-xx);
}
}
long long f(int x, int y, int z) {
long long ret = 0;
int xx = x;
while(xx > 0) {
int yy = y;
while(yy > 0) {
int zz = z;
while(zz > 0) {
ret += tree[xx][yy][zz];
zz -= zz & (-zz);
}
yy -= yy & (-yy);
}
xx -= xx & (-xx);
}
return ret;
}
long long solve(int x1, int y1, int z1, int x2, int y2, int z2){
long long j4 = f(x1-1, y1-1, z1-1);
long long j1 = f(x2, y1-1, z1-1) - j4;
long long j2 = f(x1-1, y2, z1-1) - j4;
long long j3 = f(x1-1, y1-1, z2) - j4;
return f(x2, y2, z2) - f(x2, y1-1, z2) - f(x1-1, y2, z2) - f(x2, y2, z1-1) + 2*j4 + j1 + j2 + j3;
}
int main()
{
int test;
scanf("%d", &test);
assert(test>=1);
assert(test<=50);
while(test--) {
memset(tree, 0, sizeof(tree));
int N, M;
cin >> N >> M;
assert(N>=1);
assert(N<=100);
assert(M>=1);
assert(M<=1000);
string st;
int x1, y1, z1, x2, y2, z2;
long long val;
while(M--) {
cin >> st;
assert(st == "QUERY" || st == "UPDATE");
if(st[0] == 'Q') {
cin >> x1 >> y1 >> z1;
cin >> x2 >> y2 >> z2;
assert(1 <= x1);
assert(x1 <= x2);
assert(x2 <= N);
assert(1 <= y1);
assert(y1 <= y2);
assert(y2 <= N);
assert(1 <= z1);
assert(z1 <= z2);
assert(z2 <= N);
cout << solve(x1, y1, z1, x2, y2, z2) << "\n";
}
else if (st[0] == 'U') {
cin >> x1 >> y1 >> z1 >> val;
assert(1 <= x1); assert(x1 <= N);
assert(1 <= y1); assert(y1 <= N);
assert(1 <= z1); assert(z1 <= N);
assert(-1e9 <= val);
assert(val <= 1e9);
long long existingVal = solve(x1, y1, z1, x1, y1, z1);
update(x1, y1, z1, val-existingVal);
}
}
}
return 0;
}
No comments:
Post a Comment