import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.lang.AssertionError import java.util.* import kotlin.math.abs import kotlin.math.max import kotlin.math.min val MOD = 1_000_000_007 class Solver(stream: InputStream, private val out: java.io.PrintWriter) { private val reader = BufferedReader(InputStreamReader(stream), 32768) fun solve() { val N = ni() val Q = ni() val A = na(N) val S = LongArray(N + 1) for (i in 0 until N) { S[i + 1] = S[i] + A[i] } val tree = DelayMergeTree(N) tree.build(IntArray(N + 1){1}) for (q in 0 until Q) { val type = ni() val l0 = ni() val r0 = ni() + 1 val l = tree.lowerBound(l0) val r = tree.lowerBound(r0) when(type) { 1 -> { tree.apply(l + 1, r, 0) } else -> { val ans = S[r] - S[l] out.println(ans) } } } } inner class DelayMergeTree(val n: Int) { /* fx: x同士の結合 fa: mをxに作用させる fm: 作用素を結合 fp: (x1 + x2)*fp(m, n) == x1*fp(m, n/2) + x2*fp(m, n/2) <- fxが+だったらm*n (+, +) ↓の実装は区間sum、更新はaddの場合 */ // private inline fun fx(x1: Int, x2: Int) = x1 + x2 // private inline fun ap(x: Int, m: Int) = x + m // private inline fun fm(m1: Int, m2: Int) = m1 + m2 // private inline fun fp(m: Int, n: Int) = m*n // private val zeroX = 0L // private val zeroM = 0L // private inline fun contains(k: Int, x: Int): Boolean = false /* (+, 入れ替え) */ private inline fun fx(x1: Int, x2: Int) = x1 + x2 private inline fun ap(x: Int, m: Int) = m private inline fun fm(m1: Int, m2: Int) = m2 private inline fun fp(m: Int, n: Int) = m*n private val zeroX = 0 private val zeroM = -1 private inline fun contains(k: Int, x: Int): Boolean = false /* (min, 入れ替え) こちらはmin、更新は入れ替えの場合 更新のところにifいらないかも */ // private inline fun fx(x1: Int, x2: Int) = min(x1, x2) // private inline fun ap(x: Int, m: Int) = if (m == zeroM) x else m // private inline fun fm(m1: Int, m2: Int) = if (m2 == zeroM) m1 else m2 // private inline fun fp(m: Int, n: Int) = m // private val inf = 2e18.toInt() + 100 // private val zeroX = inf // private val zeroM = inf // private inline fun contains(k: Int, x: Int): Boolean = value[k] < x /* (max, +) */ // private inline fun fx(x1: Int, x2: Int) = max(x1, x2) // private inline fun ap(x: Int, m: Int) = x + m // private inline fun fm(m1: Int, m2: Int) = m1 + m2 // private inline fun fp(m: Int, n: Int) = m // private val inf = 0L // マイナスありなら -(2e18.toInt + 100) // private val zeroX = inf // private val zeroM = inf // private inline fun contains(k: Int, x: Int): Boolean = value[k] > x /* (xor, 入れ替え) */ // private inline fun fx(x1: Int, x2: Int) = x1 or x2 // private inline fun ap(x: Int, m: Int) = m // private inline fun fm(m1: Int, m2: Int) = m2 // private inline fun fp(m: Int, n: Int) = m // private val zeroX = 0L // private val zeroM = 0L // private inline fun contains(k: Int, x: Int): Boolean = false // min/maxじゃないと使えない private val log = log2_ceil(n) private val N = 1 shl log // zeroX, zeroMよりも前にあると初期化できなくなるので注意 private val value = IntArray(N * 2){zeroX} private val delay = IntArray(N * 2){zeroM} private inline fun push(k: Int, len: Int) { if (delay[k] == zeroM) return if (k < N) { delay[k * 2] = fm(delay[k * 2], delay[k]) delay[k * 2 + 1] = fm(delay[k * 2 + 1], delay[k]) } value[k] = ap(value[k], fp(delay[k], len)) delay[k] = zeroM } private inline fun pushAll(a: Int, b: Int) { val ka = a + N val kb = b + N for (j in log downTo 1) { push(ka shr j, N shr j) push(kb shr j, N shr j) } } fun build(A: IntArray) { for (i in A.indices) { value[N + i] = A[i] } for (k in N - 1 downTo 0) { value[k] = fx(value[k*2], value[k*2 + 1]) } } /** * [a, b) */ fun apply(a: Int, b: Int, x: Int, k: Int = 1, l: Int = 0, r: Int = N) { push(k, r - l) if (a >= r || l >= b) return // ノードが範囲からはずれてる if (a <= l && r <= b) { // ノードが完全に範囲に含まれる delay[k] = fm(delay[k], x) push(k, r - l) return } val m = (l + r) / 2 val lft = k * 2 val rgt = lft + 1 apply(a, b, x, lft, l, m) apply(a, b, x, rgt, m, r) value[k] = fx(value[lft], value[rgt]) } /** * [a, b) */ fun prod(a: Int, b: Int): Int { pushAll(a, b) // 通り道のdelayを消費したので、後は普通のSegTreeと一緒 var res = zeroX var left = a + N var right = b - 1 + N while(left <= right) { if ((left and 1) == 1) res = fx(res, value[left]) if ((right and 1) == 0) res = fx(res, value[right]) left = (left + 1) shr 1 // 右の子供なら右の親に移動 right = (right - 1) shr 1 // 左の子供なら左の親に移動 } return res // pushAll(a, b) // // // delayを消費したので、後は普通のSegTreeと一緒 // // var res: Int = zeroX // var left = a + N // var right = b - 1 + N // // while(left <= right) { // if ((left and 1) == 1) res = fx(res, value[left]) // if ((right and 1) == 0) res = fx(res, value[right]) // left = (left + 1) shr 1 // 右の子供なら右の親に移動 // right = (right - 1) shr 1 // 左の子供なら左の親に移動 // } // // return res } fun get(i: Int): Int { val k = i + N for (j in log downTo 1) { push(k shr j, N shr j) } return value[k] } fun set(i: Int, x: Int) { val k = i + N for (j in log downTo 1) { push(k shr j, N shr j) } value[k] = x for (j in 1 .. log) { val kk = k shr j value[kk] = fx(value[kk*2], value[kk*2 + 1]) } } /** * @param x 左右どちらからか最初に contains になる場所を探す。containsはfxがmin/maxかで違う * @param fromR 右から探すか * @return 見つからなかったら -1 */ fun query(x: Int, k: Int = 1, l: Int = 0, r: Int = N, fromR: Boolean = true): Int { push(k, r - l) if (!contains(k, x)) return -1 if (l + 1 == r) return l val m = (l + r) / 2 val lft = k * 2 val rgt = lft + 1 if (fromR) { val ans = query(x, rgt, m, r, fromR) if (ans != -1) return ans return query(x, lft, l, m, fromR) } else { val ans = query(x, lft, l, m, fromR) if (ans != -1) return ans return query(x, rgt, m, r, fromR) } } /** * @return 最初にvalue>=xになるindexを返す。0-indexed 見つからなかったら n * fxがsum かつ 値に負がないことが条件 */ fun lowerBound(x: Int): Int { var remain = x var k = 1 var len = N var res = 0 push(1, N) for (i in 1 .. log) { push(k*2, len/2) if (value[k*2] < remain) { remain -= value[k*2] res += len/2 push(k*2 + 1, len/2) k = k*2 + 1 } else { k *= 2 } len /= 2 } return min(n, res) } fun inspect() = run { Pair(value, delay) } /** * 最初に x<=2^k になるkを返す */ fun log2_ceil(x: Int): Int { var k = 0 var pow2 = 1 while(pow2 < x) { pow2 *= 2 k++ } return k } } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private var tokenizer: StringTokenizer? = null private fun next(): String { while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { tokenizer = StringTokenizer(reader.readLine()) } return tokenizer!!.nextToken() } private fun ni() = next().toInt() private fun nl() = next().toLong() private fun ns() = next() private fun na(n: Int, offset: Int = 0): IntArray { return IntArray(n) { ni() + offset } } private fun nal(n: Int, offset: Int = 0): LongArray { val res = LongArray(n) for (i in 0 until n) { res[i] = nl() + offset } return res } private fun na2(n: Int, offset: Int = 0): Array { val a = Array(2){IntArray(n)} for (i in 0 until n) { for (e in a) { e[i] = ni() + offset } } return a } private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } /** * コーナーケースでエラー出たりするので、debug(dp[1])のように添え字付きの場合はdebug{}をつかうこと */ private inline fun debug(a: LongArray) { debug { a.joinToString(" ") } } private inline fun debug(a: IntArray) { debug { a.joinToString(" ") } } private inline fun debug(a: BooleanArray) { debug { toString(a) } } private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")} private inline fun debugDim(A: Array) { if (isDebug) { for (a in A) { debug(a) } } } private inline fun debugDim(A: Array) { if (isDebug) { for (a in A) { debug(a) } } } private inline fun debugDim(A: Array) { if (isDebug) { for (a in A) { debug(a) } } } /** * 勝手にimport消されるのを防ぎたい */ private fun hoge() { min(1, 2) max(1, 2) abs(-10) } private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()} private inline fun assert(b: Boolean, f: () -> String) = run{if (!b) throw AssertionError(f())} } fun main() { val out = java.io.PrintWriter(System.out) Solver(System.`in`, out).solve() out.flush() }