結果

問題 No.875 Range Mindex Query
ユーザー yakamoto
提出日時 2019-09-06 21:43:02
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 1,007 ms / 2,000 ms
コード長 2,296 bytes
コンパイル時間 13,268 ms
コンパイル使用メモリ 446,972 KB
実行使用メモリ 91,004 KB
最終ジャッジ日時 2024-06-24 17:20:01
合計ジャッジ時間 25,995 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import kotlin.math.max
import kotlin.math.min

// なんか本番でエラーでる
private val isDebug = runCatching {
  System.getenv("MY_DEBUG") != null
}.fold({it}, {false})

private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }.toIntArray()
private fun readLongs() = readStrings().map { it.toLong() }.toLongArray()
private fun debug(msg: () -> String) {
  if (isDebug) System.err.println(msg())
}
private fun debug(a: LongArray) {
  if (isDebug) debug{a.joinToString(" ")}
}
private fun debug(a: IntArray) {
  if (isDebug) debug{a.joinToString(" ")}
}
private fun debugDim(A: Array<IntArray>) {
  if (isDebug) {
    for (a in A) {
      debug(a)
    }
  }
}

val MOD = 1000000007

class SegmentTree(n: Int, val zero: Int, val f: (Int, Int) -> Int) {
  private val N =
    if (Integer.highestOneBit(n) == n) n
    else Integer.highestOneBit(n) shl 1

  private val dat = IntArray(2 * N){zero}

  fun update(i: Int, a: Int) {
    var ix = i + N
    dat[ix] = a
    while(ix > 1) {
      dat[ix shr 1] = f(dat[ix], dat[ix xor 1])
      ix = ix shr 1
    }
  }

  /**
    * [a, b)
    */
  fun query(a: Int, b: Int): Int {
    var res: Int = zero
    var left = a + N
    var right = b - 1 + N

    while(left <= right) {
      if ((left and 1) == 1) res = f(res, dat[left])
      if ((right and 1) == 0) res = f(res, dat[right])
      left = (left + 1) shr 1 // 右の子供なら右の親に移動
      right = (right - 1) shr 1 // 左の子供なら左の親に移動
    }

    return res
  }
}

fun main() {
  val (N, Q) = readInts()
  val A = IntArray(N + 1)
  for ((i, a) in readInts().withIndex()) {
    A[i] = a
  }
  A[N] = N + 10
  debug(A)

  val seg = SegmentTree(N, N) { a, b ->
    if (A[a] < A[b]) a else b
  }
  repeat(N) {
    seg.update(it, it)
  }

  val ans = mutableListOf<Int>()
  repeat(Q) {
    var (type, l, r) = readInts()
    l--; r--
    when(type) {
      1 -> {
        val oldL = A[l]
        val oldR = A[r]
        A[l] = oldR
        A[r] = oldL
        seg.update(l, l)
        seg.update(r, r)
        debug(A)
      }
      2 -> {
        ans += seg.query(l, r + 1) + 1
      }
    }
  }

  println(ans.joinToString("\n"))
}
0