## Algorithm

Problem Name: Data Structures - Box Operations

In this HackerRank in Data Structures - Box Operations solutions,

Alice purchased an array of n wooden boxes that she indexed from 0 to n - 1. On each box i, she writes an integer that we'll refer to as boxi . Alice wants you to perform q operations on the array of boxes. Each operation is in one of the following forms:

(Note: For each type of operations, l <= i <= r)

• 1 l r c: Add to each boxi . Note that c an be negative.
• 2 l r d: Replace each boxi with [boxi/d].
• 3 l r: Print the minimum value of any boxi.
• 4 l r: Print the sum of all boxi.

Recall that [x] is the maximum integer y such that y <= x (e.g. [-2.5] = -3 and [-7] = -7).

Given n the value of each boxi , and q operations, can you perform all the operations efficiently?

Input Format

The first line contains two space-separated integers denoting the respective values of n (the number of boxes) and q (the number of operations).
The second line contains n space-separated integers describing the respective values of box0 ,box1 , ..... , boxn-1 (i.e., the integers written on each box).
Each of the q subsequent lines describes an operation in one of the four formats defined above.

Constraints

• 1 <= n,q <= 105
• -109 <= boxi <= 109
• 0 <= l <= r <= n - 1
• -104 <= c <= 104
• 2 <= d <= 109

Output Format

For each operation of type 3 or type 4 print the answer on a new line.

Sample Input 0

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9


Sample Output 0

-2
-2
-2
-2
0
1
1


Explanation 0

Initially, the array of boxes looks like this:

We perform the following sequence of operations on the array of boxes:

1. The first operation is 1 0 4 1, so we add 1 to each  boxi where 0 <= i <= 4:
2. The second operation is 1 5 9 1, so we add c = 1 to each boxi where 5 <= i <= 9:
3. The third operation is 2 0 9 3, so we divide each boxi where 0 <= i <= 9 by d = 3 and take the floor:
4. The fourth operation is 3 0 9, so we print the minimum value of boxi for 0 <= i <= 9 , which is the result of min(-2,-1,-1,-1,0,0,0,1,1,1) = -2.
5. The fifth operation is 4 0 9, so we print the sum of boxi for 0 <= i <= 9 , which is the result of  -2 + -1 + -1 + -1 + 0 + 0 + 0 + 1 + 1 +1 = -2.
... and so on.

## Code Examples

### #1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
#define N 110000
#define M 550000
long long tmp[M], mi[M], mx[M], sum[M];
void tpl(int v, long long c, int len)
{
tmp[v] += c;
sum[v] += c * len;
mx[v] += c;
mi[v] += c;
}
void update(int v, int l, int r)
{
if(tmp[v])
{
int mid = ( l + r ) / 2;
tpl(v+v, tmp[v], mid-l+1);
tpl(v+v+1, tmp[v], r-mid);
tmp[v] = 0;
}
}
int min(int a, int b)
{
return a < b ? a : b;
}
int max(int a, int b>
{
return a > b ? a : b;
}
void add(int l, int r, int v, int x, int y, long long c)
{
if( l == x && r == y )
{
tmp[v] += c;
sum[v] += c * ( r - l + 1 );
mx[v] += c;
mi[v] += c;
return;
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
add(l, mid, v+v, x, y, c>;
}
else if( x > mid )
{
add(mid+1, r, v+v+1, x, y, c);
}
else
{
add(l, mid, v+v, x, mid, c), add(mid+1, r, v+v+1, mid+1, y, c);
}
sum[v] = sum[v+v] + sum[v+v+1];
mi[v] = min(mi[v+v], mi[v+v+1]);
mx[v] = max(mx[v+v], mx[v+v+1]);
}
const long long inf = 5e9;
int cnt;
void div(int l, int r, int v, int x, int y, long long c)
{
cnt++;
if( l == x && r == y && mi[v] >= mx[v]-1 && ( ( mi[v] + c * inf ) / c - inf - mi[v] ) == ( ( mx[v] + c * inf ) / c - inf - mx[v] ) )
{
if( mi[v] > 0 )
{
c = mi[v] / c - mi[v];
}
else
{
c = ( mi[v] + c * inf ) / c - inf - mi[v];
}
tmp[v] += c;
sum[v] += c * ( r - l + 1 );
mx[v] += c;
mi[v] += c;
return;
}
update(v, l, r);
int mid = ( l + r ) / 2;
if( y <= mid )
{
div(l, mid, v+v, x, y, c>;
}
else if( x > mid )
{
div(mid+1, r, v+v+1, x, y, c);
}
else
{
div(l, mid, v+v, x, mid, c), div(mid+1, r, v+v+1, mid+1, y, c);
}
sum[v] = sum[v+v] + sum[v+v+1];
mi[v] = min(mi[v+v], mi[v+v+1]);
mx[v] = max(mx[v+v], mx[v+v+1]);
}
long long minmize(int l, int r, int v, int x, int y)
{
if( l == x && r == y )
{
return mi[v];
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
return minmize(l, mid, v+v, x, y>;
}
else if( x > mid )
{
return minmize(mid+1, r, v+v+1, x, y);
}
else
{
return min(minmize(l, mid, v+v, x, mid), minmize(mid+1, r, v+v+1, mid+1, y));
}
}
long long get(int l, int r, int v, int x, int y)
{
if( l == x && r == y )
{
return sum[v];
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
return get(l, mid, v+v, x, y>;
}
else if( x > mid )
{
return get(mid+1, r, v+v+1, x, y);
}
else
{
return get(l, mid, v+v, x, mid) + get(mid+1, r, v+v+1, mid+1, y);
}
}
int a[N];
int main()
{
int n, q, i;
scanf("%d%d", &n, &q);
for( i = 1 ; i <= n ; i++ )
{
scanf("%d", &a[i]), add(1, n, 1, i, i, a[i]);
}
for( i = 1 ; i  < = q ; i++ )
{
int ty, l, r;
scanf("%d%d%d", &ty, &l, &r);
l++;
r++;
if( ty == 1 )
{
int c;
scanf("%d", &c);
add(1, n, 1, l, r, c);
}
if( ty == 2 )
{
int c;
scanf("%d", &c);
div(1, n, 1, l, r, c);
}
else if( ty == 3 )
{
printf("%lld\n", minmize(1, n, 1, l, r));
}
if( ty == 4 )
{
printf("%lld\n", get(1, n, 1, l, r)>;
}
if( cnt > 1e8 )
{
a[-inf] = 100;
return -1;
}
}
return 0;
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
inline int Div(int x , int d) {
return x >= 0 ? x / d : -((-x + d - 1) / d);
}

int n , m , a[N];

inline int id(int l , int r) {
return l + r | l != r;
}
#define MID int mid = l + r >> 1
#define Left l , mid
#define Right mid + 1 , r

struct stree {
int mx , mn , f;
LL s;
void add(int w , int len) {
mx += w;
mn += w;
f += w;
s += (LL)len * w;
}
} t[N << 1];

void pushdown(int p , int l , int mid , int r) {
if (t[p].f) {
t[id(Left)].add(t[p].f , mid - l + 1);
t[id(Right)].add(t[p].f , r - mid);
t[p].f = 0;
}
}
void pushup(int p , int l , int mid , int r) {
int L = id(Left) , R = id(Right);
t[p].mx = max(t[L].mx , t[R].mx);
t[p].mn = min(t[L].mn , t[R].mn);
t[p].s = t[L].s + t[R].s;
}
void build(int l , int r) {
int p = id(l , r);
t[p].f = 0;
if (l == r) {
t[p].mx = t[p].mn = t[p].s = a[l];
} else {
MID;
build(Left);
build(Right);
pushup(p , l , mid , r);
}
}
void add(int l , int r , int top , int bot , int w) {
int p = id(l , r);
if (top  < = l && r <= bot) {
t[p].add(w , r - l + 1);
} else {
MID; pushdown(p , l , mid , r);
if (top  < = mid) add(Left , top , bot , w);
if (bot > mid) add(Right , top , bot , w);
pushup(p , l , mid , r);
}
}
LL sum(int l , int r , int top , int bot) {
int p = id(l , r);
if (top  < = l && r <= bot) {
return t[p].s;
} else {
MID; pushdown(p , l , mid , r); LL res = 0;
if (top  < = mid) res += sum(Left , top , bot);
if (bot > mid) res += sum(Right , top , bot);
return res;
}
}
int minimum(int l , int r , int top , int bot) {
int p = id(l , r);
if (top  < = l && r <= bot) {
return t[p].mn;
} else {
MID; pushdown(p , l , mid , r); int res = 0x7FFFFFFF;
if (top  < = mid) res = min(res , minimum(Left , top , bot));
if (bot > mid) res = min(res , minimum(Right , top , bot));
return res;
}
}
void divide(int l , int r , int top , int bot , int d) {
int p = id(l , r);

bool stop = 0;
if (top  < = l && r <= bot) {
if (t[p].mx == t[p].mn) stop = 1;
int delta = t[p].mx - t[p].mn;
int t1 = Div(t[p].mx , d);
int t0 = Div(t[p].mn , d);
if (t1 - t0 == delta) stop = 1;
}

if (stop || l == r) {
t[p].add(Div(t[p].mx , d) - t[p].mx , r - l + 1);
} else {
MID; pushdown(p , l , mid , r);
if (top  < = mid) divide(Left , top , bot , d);
if (bot > mid) divide(Right , top , bot , d);
pushup(p , l , mid , r);
}

}

int main() {
scanf("%d%d" , &n , &m);
for (int i = 0 ; i  <  n ; ++ i) {
scanf("%d" , a + i);
}
build(0 , n - 1);
for (int i = 0 ; i  <  m ; ++ i) {
int o , l , r , w;
scanf("%d%d%d" , &o , &l , &r);
if (o == 1) {
scanf("%d" , &w);
add(0 , n - 1 , l , r , w);
}
if (o == 2) {
scanf("%d" , &w);
divide(0 , n - 1 , l , r , w);
}
if (o == 3) {
printf("%d\n" , minimum(0 , n - 1 , l , r));
}
if (o == 4) {
printf("%lld\n" , sum(0 , n - 1 , l , r));
}
}
}

Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {

static int func(int p, int q) {
if (p >= 0) {
return p / q;
}
return -((-p + q - 1) / q);
}

static final int inf = (int) (2e9) + (int) (1e8);

static class Tree {
long[] sum;
int[] vmin;
int[] vmax;
int[] add;
int base;

Tree(int n) {
base = (1 << (32 - Integer.numberOfLeadingZeros(n)));
sum = new long[base * 2];
vmin = new int[base * 2];
vmax = new int[base * 2];
add = new int[base * 2];
}

private void update(int u) {
vmin[u] = Math.min(vmin[u * 2], vmin[u * 2 + 1]);
vmax[u] = Math.max(vmax[u * 2], vmax[u * 2 + 1]);
sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

private void putVal(int u, int val, int len) {
add[u] += val;
vmin[u] += val;
vmax[u] += val;
sum[u] += val * len;
}

private void push(int u, int cl, int cr) {
if (add[u] != 0) {
int len = (cr - cl) / 2;
putVal(u * 2, add[u], len);
putVal(u * 2 + 1, add[u], len);
add[u] = 0;
}
}

long getSum(int l, int r) {
return getSum(l, r, 1, 0, base);
}

private long getSum(int l, int r, int v, int cl, int cr) {
if (l  < = cl && cr <= r) {
return sum[v];
}
if (r <= cl || cr <= l) {
return 0;
}
int cc = (cl + cr) / 2;
push(v, cl, cr);
return getSum(l, r, v * 2, cl, cc) + getSum(l, r, v * 2 + 1, cc, cr);
}

int getMin(int l, int r) {
return getMin(l, r, 1, 0, base);
}

private int getMin(int l, int r, int v, int cl, int cr) {
if (l  < = cl && cr <= r) {
return vmin[v];
}
if (r <= cl || cr <= l) {
return inf;
}
int cc = (cl + cr) / 2;
push(v, cl, cr);
return Math.min(getMin(l, r, v * 2, cl, cc), getMin(l, r, v * 2 + 1, cc, cr));
}

void put(int l, int r, int delta) {
put(l, r, delta, 1, 0, base);
}

private void put(int l, int r, int delta, int v, int cl, int cr) {
if (l  < = cl && cr <= r) {
putVal(v, delta, cr - cl);
return;
}
if (r  < = cl || cr <= l) {
return;
}
int cc = (cl + cr) / 2;
push(v, cl, cr);
put(l, r, delta, v * 2, cl, cc);
put(l, r, delta, v * 2 + 1, cc, cr);
update(v);
}

private void divide(int l, int r, int x) {
divide(l, r, x, 1, 0, base);
}

private void divide(int l, int r, int x, int v, int cl, int cr) {
if (x == 1) {
return;
}
if (l  < = cl && cr <= r) {
int d1 = func(vmin[v], x) - vmin[v];
int d2 = func(vmax[v], x) - vmax[v];
if (d1 == d2) {
putVal(v, d1, cr - cl);
return;
}
}
if (r  < = cl || cr <= l) {
return;
}
int cc = (cl + cr) / 2;
push(v, cl, cr);
divide(l, r, x, v * 2, cl, cc);
divide(l, r, x, v * 2 + 1, cc, cr);
update(v);
}

void build(int n) {
for (int i = n + base; i  <  2 * base; i++) {
vmin[i] = inf;
vmax[i] = -inf;
}
for (int i = base - 1; i > 0; i--) {
update(i);
}
}
}

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

Tree t = new Tree(n);

int[] box = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i  <  n; i++) {
int item = Integer.parseInt(st.nextToken());
box[i] = item;
t.sum[i + t.base] = t.vmin[i + t.base] = t.vmax[i + t.base] = item;
}
t.build(n);

for (int i = 0; i  <  q; i++) {
st = new StringTokenizer(br.readLine());
int op = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken()) + 1;
if (op == 1) {
int x = Integer.parseInt(st.nextToken());
t.put(l, r, x);
} else if (op == 2) {
int x = Integer.parseInt(st.nextToken());
t.divide(l, r, x);
} else if (op == 3) {
bw.write(t.getMin(l, r) + "\n");
} else if (op == 4) {
bw.write(t.getSum(l, r) + "\n");
}
}

bw.close();
br.close();
}
}

Copy The Code &
Advertisements