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 :
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
Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →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 →