求助 Kotlin

P3372 【模板】线段树 1

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


|