Box Operations


Problem Statement :


Alice purchased an array of n wooden boxes that she indexed from 0  to n - 1 . On each box , she writes an integer that we'll refer to as .

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, )

1 l r c: Add  to each . Note that  can be negative.
2 l r d: Replace each  with .
3 l r: Print the minimum value of any .
4 l r: Print the sum of all .
Recall that  is the maximum integer  such that  (e.g.,  and ).

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

Input Format

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


Constraints

1  <=  n, q <=  10^5
-10^9  <=  boxi  <=  10^9
0  <=  l  <=  r  <=  n - 1 
- 10^4  <=  c  <=  10^4
2  <=  d  <=  10^9


Output Format

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



Solution :



title-img


                            Solution in C :

in   C++  :






#include <bits/stdc++.h>
#include <limits.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF INT_MAX
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inrep int t;cin>>t; while(t--)
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll > vpll;
typedef vector<string> vs;
typedef long double ld;

template<typename T> ostream& operator<< ( 
ostream &o,vector<T> v ) {
if ( v.size() >0 )
o<<v[0];
for ( unsigned   i=1; i<v.size(); i++ )
o<<" "<<v[i];
return o<<endl;
}
template<typename U,typename V> ostream& operator<< (
     ostream &o,pair<U,V> p ) {
return o<<"("<<p.first<<", "<<p.second<<") ";
}
template<typename T> istream& operator>> ( 
    istream &in,vector<T> &v ) {

for ( unsigned   i=0; i<v.size(); i++ )
in>>v[i];
return in;
}
constexpr int BXSIZE=117;

typedef  int realt;
struct Box {
bool isSpecial=1;
int mx=BXSIZE;
array<int,BXSIZE> vals= {};
array<int,3> spVals= {};
array<int,3> cnt= {};
ll su=0;
int mi=INF,ma=-INF;


void add ( int b, int e, int c ) {
doAdd();
if ( !isSpecial ) makeSpecial();
reu ( i,b,e ) vals[i]+=c;
su+= ( ll ) ( e-b ) *c;
mi=INF, ma=-INF;

rep ( i,mx ) {
mi=min ( mi,vals[i] );
ma=max ( ma, vals[i] );
}
}
void dfloor ( int &x, realt d ) {
if ( x>0 ) {
x=x/d;
} else {
int y=x/d;
if (y*d!=x ) y--;
x=y;
}
}
void divide ( int b, int e, realt d ) {
doAdd();
if ( !isSpecial ) makeSpecial();
reu ( i,b,e ) dfloor ( vals[i],d ); //vals[i]/=d;
mi=INF, ma=-INF;
su=0;
rep ( i,mx ) {
su+=vals[i];
mi=min ( mi,vals[i] );
ma=max ( ma, vals[i] );
}
}
void divide ( realt d ) {
doAdd();
dfloor ( mi,d );
dfloor ( ma,d );
if ( isSpecial ) {
su=0;
rep ( i,mx ){
if(vals[i] &&vals[i]!=-1)dfloor ( vals[i],d );
su+=vals[i];
}
if ( ma-mi<3 ) {
makeUnspecial();
}
} else {
dfloor ( spVals[0],d );
dfloor ( spVals[1],d );
dfloor ( spVals[2],d );

su= ( ll ) cnt[0]*spVals[0]+
 ( ll ) cnt[1]*spVals[1]+ ( ll ) cnt[2]*spVals[2];
}
}

int addC=0;

void add ( int c ) {
addC+=c;
su+= ( ll ) mx*c;
mi+=c;
ma+=c;

}
void doAdd(){
if(!addC)return;
if ( isSpecial ) {
rep ( i,mx ) vals[i]+=addC;
} else {
spVals[0]+=addC;
spVals[1]+=addC;
spVals[2]+=addC;
}
addC=0;

}


ll findSum ( int b, int e ) {
doAdd();
ll su=0;
if ( isSpecial ) {
reu ( i,b,e ) {
su+=vals[i];
}
} else {
reu ( i,b,e ) {
su+=spVals[vals[i]];
}
}
return su;

}
int findMin ( int b, int e ) {
doAdd();
int mi=INF;
reu ( i,b,e ) mi=min ( mi,vals[i] );
if ( isSpecial ) return mi;
return spVals[mi];
}
void makeUnspecial() {
isSpecial=0;
spVals[0]=mi, spVals[1]=mi+1, spVals[2]=mi+2;
cnt[0]=cnt[1]=cnt[2]=0;
rep ( i,mx ) {
int d=vals[i]-mi;
vals[i]=d;
cnt[d]++;
}
}
void makeSpecial() {
isSpecial=1;
rep ( i,mx ) {
vals[i]=spVals[vals[i]];
}
}

};
#define gc getchar_unlocked

ostream &operator<< ( ostream &os, const Box &b ) {
if ( b.isSpecial ) os<<"special"<<endl;
os<<vi ( b.vals.begin(), b.vals.begin() +b.mx );
os<<"mi "<<b.mi<<" ma "<<b.ma<<"  "<<"su "<<b.su<<endl;
return os;

}

void scan ( int &x ) {
int c = gc();
x = 0;
bool inv=0;
while ( ( c<48 || c>57 ) && c!='-' )  c = gc();
if ( c=='-' ) {
inv=1;
c = gc();
}
while ( c>47 && c<58 ) {
x = ( x << 1 ) + ( x << 3 ) + c - 48;
c = gc();
}
if ( inv ) x=-x;
}
void dump ( vector<Box> &b ) {
rep ( i,b.size() ) {
cout<<"Box "<<i<<endl;
cout<<b[i];
}

}
int main() {

int n;
scan ( n );
int q;
scan ( q );
int nBoxes= ( n-1 ) /BXSIZE+1;
vector<Box> boxes ( nBoxes );
int j=0;
int k=0;
rep ( i,n ) {
int x;
scan ( x );
boxes[k].vals[j]=x;
boxes[k].mi=min ( boxes[k].mi,x );
boxes[k].ma=max ( boxes[k].ma,x );
boxes[k].su+=x;
if ( ++j==BXSIZE ) {
k++;
j=0;
}
}
if ( j ) boxes.back().mx=j;
vll res;
rep ( i,q ) {
int t, l,r,x;
scan ( t );
scan ( l );
scan ( r );
r++;
int bmi=l/BXSIZE;
int bma= ( r-1 ) /BXSIZE;
int bi=l-bmi*BXSIZE;
int be=r-bma*BXSIZE;
if ( t<3 ) scan ( x );
if ( t==1 ) {
if ( bmi==bma ) {
boxes[bmi].add ( bi,be, x );
} else {
boxes[bmi].add ( bi, boxes[bmi].mx,x );
reu ( i,bmi+1, bma ) {
boxes[i].add ( x );
}
boxes[bma].add ( 0,be,x );
}

} else if ( t==2 ) {
realt y=x; //1.0/x;
if ( bmi==bma ) {
boxes[bmi].divide ( bi,be, y );
} else {
boxes[bmi].divide ( bi, boxes[bmi].mx,y );
reu ( i,bmi+1, bma ) {
boxes[i].divide ( y );
}
boxes[bma].divide ( 0,be,y );
}

} else if ( t==3 ) {
int mi=INF;
if ( bmi==bma ) {
mi= boxes[bmi].findMin ( bi,be );
} else {
mi= boxes[bmi].findMin ( bi, boxes[bmi].mx );
reu ( i,bmi+1, bma ) {
mi=min ( mi,   boxes[i].mi );
}
mi=min ( mi,  boxes[bma].findMin ( 0,be ) );
}
res.push_back ( mi );

} else if ( t==4 ) {
ll su=0;
if ( bmi==bma ) {
su= boxes[bmi].findSum ( bi,be );
} else {
su= boxes[bmi].findSum ( bi, boxes[bmi].mx );
reu ( i,bmi+1, bma ) {
su+=boxes[i].su;

}
su+=  boxes[bma].findSum ( 0,be );
}
res.push_back ( su );

}
}
for ( ll r: res ) printf ( "%lld\n", r );



}








In   Java  :






import java.io.*;
//import java.lang.*;

import java.util.*;


public class Solution {
private static String inputFilename = "src/input.txt";
private static String outputFilename = "src/output.txt";
private BufferedReader in;
private StringTokenizer line;
private PrintWriter out;
private boolean isDebug;

public Solution(boolean isDebug) {
this.isDebug = isDebug;
}

public void solve() throws IOException {
int n = nextInt();
int q = nextInt();
int[] a = nextIntArray(n);
SqrtDecomposition b = new SqrtDecomposition(a);
for (int z = 0; z < q; z++) {
int op = nextInt();
int l = nextInt();
int r = nextInt();
if (op == 1) {
int c = nextInt();
b.fadd(l, r, c);


} else if (op == 2) {
int d = nextInt();
b.fdiv(l, r, d);


} else if (op == 3) {
out.println(b.fmin(l, r));


} else {
out.println(b.fsum(l, r));
}
}
}


private static class MyTimer {
private double accumulated = 0;
private long lastTime = 0;

private MyTimer() {
reset();
}

public void reset() {
lastTime = System.currentTimeMillis();
}

public long getMillisAndReset() {
long current = System.currentTimeMillis();
long result = current - lastTime;
lastTime = current;
return result;
}

public String getStrAndReset() {
return String.format(Locale.ENGLISH, "%.3fs", 
getMillisAndReset() / 1000.0);
}

public long getMillis() {
return System.currentTimeMillis() - lastTime;
}

public void accumulateMillis() {
accumulated += (
System.currentTimeMillis() - lastTime) / 1000.0;
}

public String getStr() {
return String.format(Locale.ENGLISH, "%.3fs", 
getMillis() / 1000.0);
}
}

private static TreeMap<String, 
MyTimer> profiler = new TreeMap<>();

{
profiler.put("op1", new MyTimer());
profiler.put("op2", new MyTimer());
profiler.put("op3", new MyTimer());
profiler.put("op4", new MyTimer());
}

private static void resetTimer(String s) {
MyTimer t = profiler.get(s);
if (t == null) profiler.put(s, t = new MyTimer());
t.reset();
}

private static void accumulateTimer(String s) {
profiler.get(s).accumulateMillis();
}


public void solve1() throws IOException {
Random random = new Random(20);
int n = 100000;//nextInt();
int q = 100000;//nextInt();
int[] a = new int[n];//nextIntArray(n);
for (int i = 0; i < n; i++) {
a[i] = random.nextInt(2000000000) - 1000000000;
}
resetTimer("full");
resetTimer("createSqrt");
SqrtDecomposition b = new SqrtDecomposition(a);
accumulateTimer("createSqrt");
for (int z = 0; z < q; z++) {
int op = random.nextInt(4) + 1;//nextInt();
int r = random.nextInt(n);//nextInt();
int l = random.nextInt(r + 1);//nextInt();
resetTimer("op" + op);
if (op == 1) {
int c = random.nextInt(20000) - 10000;//nextInt();
b.fadd(l, r, c);
} else if (op == 2) {
int d = random.nextInt(5) + 2;//nextInt();
b.fdiv(l, r, d);
} else if (op == 3) {
b.fmin(l, r);
//                out.println(b.fmin(l, r));
} else {
b.fsum(l, r);
//                out.println(b.fsum(l, r));
}
accumulateTimer("op" + op);
}
accumulateTimer("full");
for (Map.Entry<String, MyTimer> e : profiler.entrySet()) {
out.println(e.getKey() + " " + String.format(
    Locale.ENGLISH, "%.3fs", e.getValue().accumulated));
}
}


public void solve2() throws IOException {
Random random = new Random(40);
int n = 10;//nextInt();
int q = 40;//nextInt();
out.println(n + " " + q);
int[] a = new int[n];//nextIntArray(n);
for (int i = 0; i < n; i++) {
a[i] = random.nextInt(30) - 15;
}
out.println(Arrays.toString(a));
SqrtDecomposition b = new SqrtDecomposition(a);
for (int z = 0; z < q; z++) {
int op = random.nextInt(4) + 1;//nextInt();
int r = random.nextInt(n);//nextInt();
int l = random.nextInt(r + 1);//nextInt();
out.print(op + " " + l + " " + r + " ");
if (op == 1) {
int c = random.nextInt(30) - 15;//nextInt();
out.print(c + " ");
b.fadd(l, r, c);

for (int j = l; j <= r; j++) {
a[j] += c;
}
} else if (op == 2) {
int d = random.nextInt(5) + 2;//nextInt();
out.print(d + " ");
b.fdiv(l, r, d);

for (int j = l; j <= r; j++) {
a[j] = a[j] / d + (a[j] % d < 0 ? -1 : 0);
}
} else if (op == 3) {
long res1 = b.fmin(l, r);

long res2 = a[l];
for (int j = l; j <= r; j++) {
res2 = Math.min(res2, a[j]);
}
out.print(" ================= " + res1 + " " + res2 + " ");
if (res1 != res2) {
out.print("!!!!!!!!!!!!");
}
} else {
long res1 = b.fsum(l, r);

long res2 = 0;
for (int j = l; j <= r; j++) {
res2 += a[j];
}
out.print(" ================= " + res1 + " " + res2 + " ");
if (res1 != res2) {
out.print("!!!!!!!!!!!!");
}
}
out.println();
}
}

private static int div(int a, int b) {
return a / b + (a % b < 0 ? -1 : 0);
}

private static class MyInteger implements Comparable<MyInteger> 
{
private int value;

public MyInteger(int value) {
this.value = value;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) 
return false;

MyInteger myInteger = (MyInteger) o;

return value == myInteger.value;

}

@Override
public int hashCode() {
return value;
}

@Override
public String toString() {
return "" + value;
}

@Override
public int compareTo(MyInteger o) {
return value - o.value;
}
}

private static void add(Map<MyInteger, 
IntList> a, int v0, int idx0) {
MyInteger v = new MyInteger(v0);
IntList t = a.get(v);
if (t == null) {
a.put(v, t = new IntList());
}
t.add(idx0);
}

private static class IntList {
private int[] a;
private int n;

public IntList() {
n = 0;
a = new int[1];
}

public void add(int value) {
if (n == a.length) {
int newSize = a.length + 5;
newSize = newSize * 5 / 4;
a = Arrays.copyOf(a, newSize);
}
a[n++] = value;
}

public void addAll(IntList list) {
if (n + list.n > a.length) {
a = Arrays.copyOf(a, a.length + list.a.length);
}
System.arraycopy(list.a, 0, a, n, list.n);
n += list.n;
}

public static IntList create(int value) {
IntList res = new IntList();
res.add(value);
return res;
}
}

private static class SqrtDecomposition {
private int n;
private int len;
private int[] a;
private int[] add;
private int[] min;
private long[] sum;
private Map<MyInteger, IntList>[] nums;

public SqrtDecomposition(int[] b) {
n = b.length;
len = Math.max(1, (int) Math.sqrt(n));
a = Arrays.copyOf(b, n);
int sz = n / len + (n % len == 0 ? 0 : 1);
add = new int[sz];
min = new int[sz];
nums = new Map[sz];
for (int i = 0; i < sz; i++) {
min[i] = Integer.MAX_VALUE;
}
sum = new long[sz];
for (int i = 0; i < n; i++) {
int j = i / len;
min[j] = Math.min(min[j], a[i]);
sum[j] += a[i];
}
}

private void push(int x) {
if (nums[x] == null) {
if (add[x] != 0) {
for (int i = x * len, to = Math.min(n,
 (x + 1) * len); i < to; i++) {
a[i] += add[x];
}
}
} else {
for (Map.Entry<MyInteger, IntList> e : nums[x].entrySet()) {
int value = e.getKey().value + add[x];
IntList t = e.getValue();
for (int i = 0; i < t.n; i++) {
a[t.a[i]] = value;
}
}
}
add[x] = 0;
nums[x] = null;
}

public void fadd(int l, int r, int value) {
int cl = l / len;
int cr = r / len;
if (cl == cr) {
if (l % len == 0 && (r + 1) % len == 0) {
add[cl] += value;
min[cl] += value;
sum[cl] += len * (long) value;
} else {
push(cl);
sum[cl] += (r - l + 1) * (long) value;
for (int i = l; i <= r; i++) {
a[i] += value;
}
min[cl] = Integer.MAX_VALUE;
for (int i = cl * len, to = Math.min(n, 
(cl + 1) * len); i < to; i++) {
min[cl] = Math.min(min[cl], a[i]);
}
}
} else {
fadd(l, (cl + 1) * len - 1, value);
for (int i = cl + 1; i < cr; i++) {
fadd(i * len, (i + 1) * len - 1, value);
}
fadd(cr * len, r, value);
}
}

public void fdiv(int l, int r, int value) {
int cl = l / len;
int cr = r / len;
if (cl == cr) {
if (l % len == 0 && (r + 1) % len == 0) {
min[cl] = div(min[cl], value);

Map<MyInteger, IntList> tmp = new TreeMap<>();
sum[cl] = 0;
if (nums[cl] != null) {
for (Map.Entry<MyInteger, IntList> e : nums[cl].entrySet()) {
MyInteger v = new MyInteger(div(
    e.getKey().value + add[cl], value));
sum[cl] += e.getValue().n * (long) v.value;
IntList t = tmp.get(v);
if (t == null) {
    tmp.put(v, e.getValue());
} else {
    if (t.n > e.getValue().n) {
        t.addAll(e.getValue());
    } else {
        e.getValue().addAll(t);
        tmp.put(v, e.getValue());
    }
}
}
} else {
for (int i = cl * len, to = Math.min(n,
 (cl + 1) * len); i < to; i++) {
MyInteger v = new MyInteger(
    div(a[i] + add[cl], value));
sum[cl] += v.value;
add(tmp, v.value, i);
}
}
nums[cl] = tmp;
add[cl] = 0;
} else {
push(cl);
for (int i = l; i <= r; i++) {
a[i] = div(a[i], value);
}
sum[cl] = 0;
min[cl] = Integer.MAX_VALUE;
for (int i = cl * len, to = Math.min(
    n, (cl + 1) * len); i < to; i++) {
min[cl] = Math.min(min[cl], a[i]);
sum[cl] += a[i];
}
}
} else {
fdiv(l, (cl + 1) * len - 1, value);
for (int i = cl + 1; i < cr; i++) {
fdiv(i * len, (i + 1) * len - 1, value);
}
fdiv(cr * len, r, value);
}
}

public int fmin(int l, int r) {
int cl = l / len;
int cr = r / len;
push(cl);
push(cr);
int res = Integer.MAX_VALUE;
if (cl == cr) {
for (int i = l; i <= r; i++) {
res = Math.min(res, a[i]);
}
} else {
for (int i = l, to = (cl + 1) * len; i < to; i++) {
res = Math.min(res, a[i]);
}
for (int i = cl + 1; i < cr; i++) {
res = Math.min(res, min[i]);
}
for (int i = cr * len; i <= r; i++) {
res = Math.min(res, a[i]);
}
}
return res;
}

public long fsum(int l, int r) {
int cl = l / len;
int cr = r / len;
push(cl);
push(cr);
long res = 0;
if (cl == cr) {
for (int i = l; i <= r; i++) {
res += a[i];
}
} else {
for (int i = l, to = (cl + 1) * len; i < to; i++) {
res += a[i];
}
for (int i = cl + 1; i < cr; i++) {
res += sum[i];
}
for (int i = cr * len; i <= r; i++) {
res += a[i];
}
}
return res;
}
}

public static void main(String[] args) 
throws IOException {
new Solution(Arrays.asList(args).contains(
    "DEBUG_MODE")).run(args);
}

public void run(String[] args) throws IOException {
if (isDebug) {
in = new BufferedReader(
    new InputStreamReader(
        new FileInputStream(inputFilename)));
//            in = new BufferedReader(new InputStreamReader(System.in));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
}
out = new PrintWriter(System.out);
//        out = new PrintWriter(outputFilename);

//        int t = nextInt();
int t = 1;
for (int i = 0; i < t; i++) {
//            out.print("Case #" + (i + 1) + ": ");
solve();
}

in.close();
out.flush();
out.close();
}

private int[] nextIntArray(int n) 
throws IOException {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

private long[] nextLongArray(int n)
 throws IOException {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

private double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}

private String nextToken() throws IOException {
while (line == null || !line.hasMoreTokens()) {
line = new StringTokenizer(in.readLine());
}
return line.nextToken();
}
}








In    C   :






#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;
}







In   Python3  :





#!/bin/python3

import sys
import math

n,q = input().strip().split(' ')
n,q = [int(n),int(q)]
box = list(map(int, input().strip().split(' ')))
# your code goes here
for i in range(q):
    operation = list(map(int, input().strip().split(' ')))
    operation_type = operation[0]
    if operation_type == 1:
        for j in range(operation[1], operation[2]+1):
            box[j] = box[j] + operation[3]
    elif operation_type == 2:
        for j in range(operation[1], operation[2]+1):
            box[j] = math.floor(box[j] / operation[3])
    elif operation_type == 3:
        print(min(box[operation[1]:operation[2]+1]))
    elif operation_type == 4:
        print(sum(box[operation[1]:operation[2]+1]))
                        








View More Similar Problems

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →

Print the Elements of a Linked List

This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode

View Solution →

Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink

View Solution →

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →