bulijoijiodibuliduo @ 2023-12-08 11:14:39
MLE 三个点,有没有大佬指点一下。
val maxn = 200010
var t = Array<Long>(maxn * 2){0L}
var lz = Array<Long>(maxn * 2){0L}
var a = Array<Int>(maxn){0}
fun up(x: Int, l: Int, r: Int) {
val mid = (l + r) / 2
t[x] = t[mid * 2] + t[mid * 2 + 1]
}
fun apply(x: Int, l: Int, r: Int, v: Long) { t[x] += (r - l + 1).toLong() * v; lz[x] += v }
fun down(x: Int, l: Int, r: Int) {
val mid = (l + r) / 2
if (lz[x] != 0L) {
apply(mid * 2, l, mid, lz[x])
apply(mid * 2 + 1, mid + 1, r, lz[x])
lz[x] = 0L
}
}
fun qry(x: Int, l: Int, r: Int, a: Int, b: Int): Long {
if (a > r || l > b) return 0L
if (a <= l && r <= b) return t[x]
val mid = (l + r) / 2; down(x, l, r)
return qry(mid * 2, l, mid, a, b) + qry(mid * 2 + 1, mid + 1, r, a, b)
}
fun upd(x: Int, l: Int, r: Int, a: Int, b: Int, v: Int) {
if (a > r || l > b) return
if (a <= l && r <= b) return apply(x, l, r, v.toLong())
val mid = (l + r) / 2
down(x, l, r); upd(mid * 2, l, mid, a, b, v)
upd(mid * 2 + 1, mid + 1, r, a, b, v); up(x, l, r)
}
fun main() {
var (n, q) = readln().split(' ').map { it.toInt() }
var tmp = readln().split(' ').map { it.toIntOrNull() }
for (i in 1 .. n) a[i] = tmp[i - 1] as Int
for (i in 1 .. n) upd(1, 1, n, i, i, a[i])
while (q-- > 0) {
var op = readln().split(' ').map { it.toInt() }
if (op[0] == 1) {
upd(1, 1, n, op[1], op[2], op[3])
} else {
println(qry(1, 1, n, op[1], op[2]))
}
}
}
by bulijoijiodibuliduo @ 2023-12-08 11:19:10
maxn 改 1e5 也还是 MLE