# Counting Special Sub-Cubes

### Problem Statement :

```Given an n*n*n cube, let f(x,y,z) (where 1 <= x,y,z <= n) denote the value stored in cell (x,y,z).

A k*k*k sub-cube (where 1 <= k <= n) of an n*n*n cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to k.

For each k in the inclusive range [1,n], calculate the number of special sub-cubes. Then print each (count)k as a single line of space-separated integers (i.e., count1,count2,...,countn).

Input Format

The first line contains an integer, q, denoting the number of queries. The 2.q subsequent lines describe each query over two lines:

1.The first line contains an integer, n, denoting the side length of the initial cube.
2.The second line contains n^3 space-separated integers describing an array of n^3 integers in the form a0,a1,...,a(n^3-1). The integer in some cell (x,y,z) is calculated using the formula a[(x-1).n^2 + (y-1).n + z].

Constraints
1 <= q <= 5
1 <= n <= 50
1 <= f(x,y,z) <=n where 1 <= x,y,z <=n
Output Format

For each query, print n space-separated integers where the ith integer denotes the number of special sub-cubes for k=i.```

### Solution :

```                            ```Solution in C :

In C++ :

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>

using namespace std;
typedef long long ll;
const int MAXN = 52;

int Q;
int N;
int val[MAXN][MAXN][MAXN];
int dp[MAXN][MAXN][MAXN];

int main()
{
cin >> Q;
for (int test = 0; test < Q; test++)
{

cin >> N;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
for (int k = 0; k < MAXN; k++)
val[i][j][k] = dp[i][j][k] = 0;

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
{
cin >> val[i][j][k];
dp[i][j][k] = val[i][j][k];
}

for (int i = 1; i <= N; i++)
{
int ans = 0;
for (int j = 0; j <= N - i; j++)
for (int k = 0; k <= N - i; k++)
for (int l = 0; l <= N - i; l++)
{
if (dp[j][k][l] == i) ans++;

for (int m = 0; m < 2; m++)
for (int n = 0; n < 2; n++)
for (int o = 0; o < 2; o++)
dp[j][k][l] = max (dp[j][k][l], dp[j+m][k+n][o+l]);

}

cout << ans;
if (i < N)
cout << " ";
}
cout << "\n";
}
return 0;
}

In Java :

import java.io.IOException;

/**
*
* @author jin
*/
public class Solution {

public static void main(String args[]) throws Exception {

int q = input();
for (int i = 0; i < q; i++) {
int n = input();
int ans[] = new int[n];

int b = n * n * n, c = n * n;
int arr[][][] = new int;
int crr[][][] = new int;
int ck[] = new int[b];
input(ck, b);
int count=0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++) {
arr[j][k][l] = ck[count++];
//        System.out.print(arr[j][k][l]+" ");
if (arr[j][k][l] == 1) {
ans++;
}

}
//      System.out.println();
}
//    System.out.println("");

}
System.out.print(ans + " ");
for (int p = 1; p < n; p++) {

for (int l = 0; l < n - p; l++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[j][k][l + 1] > arr[j][k][l]) {
arr[j][k][l] = arr[j][k][l + 1];
}

}

}
}
for (int l = 0; l < n - p; l++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n-p; k++) {
//  crr[j][l][k] = arr[j][l][k];
if (arr[j][l + 1][k] > arr[j][l][k]) {
arr[j][l][k] = arr[j][l + 1][k];
}

}

}
}
for (int l = 0; l < n - p; l++) {
for (int j = 0; j < n-p; j++) {
for (int k = 0; k < n-p; k++) {
if (arr[l + 1][j][k] > arr[l][j][k]) {
arr[l][j][k] = arr[l + 1][j][k];
}

}

}
}

for (int l = 0; l < n - p; l++) {
for (int j = 0; j < n-p; j++) {
for (int k = 0; k < n-p; k++) {
//   System.out.println(l+" "+j+" "+k+"  "+(p+1));
if(arr[j][k][l]==p+1)
ans[p]++;
}
}
}

System.out.print(ans[p] + " ");

}
System.out.println();
}

}

System.in));
private static String s[], w;

public static void input(int a[], int p) throws IOException {
int i;
for (i = 0; i < p; i++) {
a[i] = Integer.parseInt(s[i]);
}

}

public static void input(long a[], int p) throws IOException {
int i;
for (i = 0; i < p; i++) {
a[i] = Long.parseLong(s[i]);
}
}

public static void input(double a[], int p) throws IOException {
int i;
for (i = 0; i < p; i++) {
a[i] = Double.parseDouble(s[i]);
}
}

public static int input() throws IOException {
int a;
return a;
}

}

In C :

#include<stdio.h>

int cube(int x,int y,int z,int size,int count[],int table,int n,int arr[])
{
if(table[x][y][z][size-1]==0)
{
if(size==1)
table[x][y][z] = arr[(x*n*n) + (y*n) +(z+1)];
else
{
int max =  0;
int a = cube(x,y,z,size-1,count,table,n,arr);
if(a>max)
max =a;
int b = cube(x+1,y,z,size-1,count,table,n,arr);
if(b>max)
max  = b;
int c = cube(x,y+1,z,size-1,count,table,n,arr);
if(c>max)
max =c;
int d= cube(x+1,y+1,z,size-1,count,table,n,arr);
if(d>max)
max = d;
int e= cube(x,y,z+1,size-1,count,table,n,arr);
if(e>max)
max = e;
int f= cube(x+1,y,z+1,size-1,count,table,n,arr);
if(f>max)
max = f;
int g= cube(x,y+1,z+1,size-1,count,table,n,arr);
if(g>max)
max = g;
int h= cube(x+1,y+1,z+1,size-1,count,table,n,arr);
if(h>max)
max = h;
table[x][y][z][size-1]=max;
}
if(table[x][y][z][size-1]==size)
count[size-1]++;
}
return table[x][y][z][size-1];
}

int main()
{
int query;
scanf("%d",&query);
while(query--)
{
int n,i;
scanf("%d",&n);
int arr[(n*n*n)+1];
for(i=1;i<=(n*n*n);i++)
scanf("%d",&arr[i]);
int table = {0};
int count[n];
for(i=0;i<n;i++)
count[i] =0;
int p= cube(0,0,0,n,count,table,n,arr);
for(i=0;i<n;i++)
printf("%d ",count[i]);
printf("\n");
}
}

In Python3 :

def findMax(arr, s, indices, n):
largest = 1
for i in indices:
cur = arr[s+i]
if cur > largest:
largest = cur
elif cur == n:
largest = n
break
return largest

def findSpecial(arr, k, n):
temp = arr
if k > 1:
temp = []
m = n - k + 2
m2 = m*m
indices = [0, 1, m, m+1, m2, m2+1, m2+m, m2+m+1]
for i in range(m-1):
start = m2*i
for j in range(m-1):
for z in range(m-1):
largest = findMax(arr, start, indices, n)
temp.append(largest)
start += 1
start += 1
return temp

q = int(input())
for _ in range(q):
n = int(input())
arr = list(map(int, input().split()))
for k in range(1, n+1):
arr = findSpecial(arr, k, n)
print(arr.count(k), end=' ')
print('')```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty