結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー nadeshino
提出日時 2020-01-25 15:43:33
言語 Nim
(2.2.0)
結果
AC  
実行時間 275 ms / 2,000 ms
コード長 3,468 bytes
コンパイル時間 4,397 ms
コンパイル使用メモリ 72,832 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-14 04:06:35
合計ジャッジ時間 6,546 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import algorithm, complex, macros, math, sequtils, sets, strutils, tables
import sugar

macro unpack*(rhs: seq, cnt: static[int]): auto =
  let v = genSym(); result = quote do:(let `v` = `rhs`;())
  if NimMajor == 0 and NimMinor <= 17:
    for i in 0 ..< cnt: result[0][1].add(quote do:`v`[`i`])
  else:
    for i in 0 ..< cnt: result[1].add(quote do:`v`[`i`])

template input*(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseint)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc `|=`*(n: var int, m: int) = n = n or m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
proc `%=`*(n: var int, m: int) = n = n mod m
proc `/=`*(n: var int, m: int) = n = n div m
proc `<<=`*(n: var int, m: int) = n = n shl m
proc `>>=`*(n: var int, m: int) = n = n shr m
proc `<?=`*(n: var SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))

# -------------------------------------------------- #

type
  MergeOperator[T] = proc(a: T, b: T): T
  SegmentTree[T] = object
    node: seq[T]
    identityElement: T
    nodeCount: Natural
    innerNodeCount: Natural
    leafNodeCount: Natural 
    merge: MergeOperator[T]
 
proc initSegmentTree*[T](n: Natural, identityElement: T, merge: MergeOperator[T]): SegmentTree[T] =
  var n = nextPowerOfTwo(n)
  result.node = newSeqWith(2 * n, identityElement)
  result.identityElement = identityElement
  result.nodeCount = 2 * n - 1
  result.innerNodeCount = n - 1
  result.leafNodeCount = n
  result.merge = merge
 
proc update*[T](self: var SegmentTree[T], x: Natural, value: T) =
  var idx = (x + self.innerNodeCount)
  self.node[idx] = value
  while idx > 1:
    idx = idx div 2
    self.node[idx] = self.merge(self.node[idx * 2], self.node[idx * 2 + 1])

proc query*[T](self: var SegmentTree[T], l: Natural, r: Natural): T =
  # [l, r]
  var l = l + self.innerNodeCount
  var r = r + self.innerNodeCount + 1
  var leftResult = self.identityElement
  var rightResult = self.identityElement
  while l < r:
    if l mod 2 == 1:
      leftResult = self.merge(leftResult, self.node[l])
      inc l
    if r mod 2 == 1:
      dec r
      rightResult = self.merge(self.node[r], rightResult)
    l = l div 2
    r = r div 2
  result = self.merge(leftResult, rightResult)

# -------------------------------------------------- #

const INF = 10 ^ 6
let (N, Q) = input(int, 2)
var A = @[0] & input(seq[int])
var seg = initSegmentTree[int](N, INF, ((n1: int, n2: int) => (min(n1, n2))))
var place = newSeq[int](N + 1)
for i, a in A:
  place[a] = i
  seg.update(i, a)

for _ in 1 .. Q:
  let (T, L, R) = input(int, 3)
  if T == 1:
    swap(place[A[L]], place[A[R]])
    swap(A[L], A[R])
    seg.update(L, A[L])
    seg.update(R, A[R])
  elif T == 2:
    echo place[seg.query(L, R)]
0