In this HackerRank Box Operations problem solution, we are given n the value of each box and q operations. we need to perform all the operations efficiently.

HackerRank Box Operations problem solution


Problem solution in 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();
  }
}


Problem solution in 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));
        }
    }
}


Problem solution in 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;
}