#634476 (Nim) No.1441 MErGe

• 問題: No.1441 MErGe
• ユーザー: zer0-star
• 提出日時: 2021-03-26 21:59:18
• 言語: Nim (2.2.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 13,828 bytes
• コンパイル時間: 1,846 ms
• コンパイル使用メモリ: 87,804 KB
• 最終ジャッジ日時: 2024-11-15 00:57:46
• 合計ジャッジ時間: 4,910 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

コンパイルメッセージ

/home/judge/data/code/Main.nim(477, 13) Error: undeclared identifier: 'N'

ソースコード

# ========= utils/base.nim ========= {{{

when not declared(INCLUDE_GUARD_UTILS_BASE_NIM):
  const INCLUDE_GUARD_UTILS_BASE_NIM = 1
  import macros
  macro Please(x): untyped = nnkStmtList.newTree()

  Please give me AC
  Please give me AC
  Please give me AC

  {.hints: off, checks: off, overflowChecks: on.}

  include prelude
  import sequtils, math, algorithm, strformat, bitops
  when (not (NimMajor <= 0)) or NimMinor >= 19:
    import sugar
  else:
    import future

  iterator range(x, y: int): int {.inline.} =
    var res = x
    while res < y:
      yield res
      inc(res)
  iterator range(x: int): int {.inline.} =
    var res = 0
    while res < x:
      yield res
      inc(res)
  proc range(x, y: int): seq[int] {.inline.} =
    toSeq(x..y-1)
  proc range(x: int): seq[int] {.inline.} =
    toSeq(0..x-1)
  proc discardableId[T](x: T): T {.inline, discardable.} =
    return x
  macro `:=`(x, y: untyped): untyped =
    if (x.kind == nnkIdent):
      return quote do:
        when declaredInScope(`x`):
          `x` = `y`
        else:
          var `x` = `y`
        discardableId(`x`)
    else:
      return quote do:
        `x` = `y`
        discardableId(`x`)
  when NimMajor <= 0 and NimMinor <= 17:
    proc count[T](co: openArray[T]; obj: T): int =
      for itm in items(co):
        if itm == obj:
          inc result
  proc divmod(x, y: SomeInteger): (int, int) =
    (x div y, x mod y)
  proc `min=`[T](x: var T; y: T): bool {.discardable.} =
    if x > y:
      x = y
      return true
    else:
      return false
  proc `max=`[T](x: var T; y: T): bool {.discardable.} =
    if x < y:
      x = y
      return true
    else:
      return false

  when NimMajor <= 0 and NimMinor <= 17:
    iterator pairs(n: NimNode): (int, NimNode) {.inline.} =
      for i in 0 ..< n.len:
        yield (i, n[i])

  #[
  when NimMajor <= 0 and NimMinor <= 18:
    macro parseInnerType(x: NimNode): untyped =
      newIdentNode("parse" & x[1][1].repr)
  else:
    macro parseInnerType(x: typedesc): untyped =
      newIdentNode("parse" & x.getType[1][1].repr)
  ]#

  proc parseInnerType(x: NimNode): NimNode =
    newIdentNode("parse" & x[1].repr)

  proc inputAsTuple(ty: NimNode): NimNode =
    result = nnkStmtListExpr.newTree()
    t := genSym()
    result.add quote do: (let `t` = stdin.readLine.split)
    p := nnkPar.newTree()
    for i, typ_tmp in ty.pairs:
      var ece, typ: NimNode
      if typ_tmp.kind == nnkExprColonExpr:
        ece = nnkExprColonExpr.newTree(typ_tmp[0])
        typ = typ_tmp[1]
      else:
        ece = nnkExprColonExpr.newTree(ident("f" & $i))
        typ = typ_tmp
      if typ.repr == "string":
        ece.add quote do: `t`[`i`]
      else:
        parsefn := newIdentNode("parse" & typ.repr)
        ece.add quote do: `t`[`i`].`parsefn`
      p.add ece
    result.add p

  macro inputAsType(ty: untyped): untyped =
    if ty.kind == nnkBracketExpr:
      if ty[1].repr == "string":
        return quote do: stdin.readLine.split
      else:
        parsefn := parseInnerType(ty)
        return quote do: stdin.readLine.split.map(`parsefn`)
        #[
          when NimMajor <= 0 and NimMinor <= 18:
            stdin.readLine.split.map(parseInnerType(ty.getType))
          else:
            stdin.readLine.split.map(parseInnerType(ty))
        ]#
    elif ty.kind == nnkPar:
      return inputAsTuple(ty)
    elif ty.repr == "string":
      return quote do: stdin.readLine
    else:
      parsefn := ident("parse" & ty.repr)
      return quote do: stdin.readLine.`parsefn`

  macro input(query: untyped): untyped =
    doAssert query.kind == nnkStmtList
    result = nnkStmtList.newTree()
    letSect := nnkVarSection.newTree()
    for defs in query:
      if defs[0].kind == nnkIdent:
        tmp := nnkIdentDefs.newTree(defs[0], newEmptyNode())
        typ := defs[1][0]
        var val: NimNode
        if typ.len <= 2:
          val = quote do: inputAsType(`typ`)
        else:
          op := typ[2]
          typ.del(2, 1)
          val = quote do: inputAsType(`typ`).mapIt(`op`)
        if defs[1].len > 1:
          op := defs[1][1]
          it := ident"it"
          tmp.add quote do:
            block:
              var `it` = `val`
              `op`
        else:
          tmp.add val
        letSect.add tmp
      elif defs[0].kind == nnkPar:
        vt := nnkVarTuple.newTree()
        for id in defs[0]:
          vt.add id
        vt.add newEmptyNode()
        sle := nnkStmtListExpr.newTree()
        t := genSym()
        sle.add quote do: (let `t` = stdin.readLine.split)
        p := nnkPar.newTree()
        if defs[1][0].kind == nnkPar:
          for i, typ in defs[1][0].pairs:
            if typ.repr == "string":
              p.add quote do: `t`[`i`]
            else:
              parsefn := newIdentNode("parse" & typ.repr)
              p.add quote do: `t`[`i`].`parsefn`
        else:
          typ := defs[1][0]
          if typ.repr == "string":
            for i in 0..<defs[0].len:
              p.add quote do: `t`[`i`]
          else:
            parsefn := newIdentNode("parse" & typ.repr)
            for i in 0..<defs[0].len:
              p.add quote do: `t`[`i`].`parsefn`
        sle.add p
        vt.add sle
        letSect.add vt
      elif defs[0].kind == nnkBracketExpr:
        ids := nnkIdentDefs.newTree(defs[0][0], newEmptyNode())
        cnt := defs[0][1]
        typ := defs[1][0]
        var input: NimNode
        if typ.kind == nnkBracketExpr and typ.len > 2:
          op := typ[2]
          typ.del(2, 1)
          input = quote do: inputAsType(`typ`).mapIt(`op`)
        else:
          input = quote do: inputAsType(`typ`)
        var val: NimNode
        if defs[0].len > 2:
          op := defs[0][2]
          it := ident"it"
          val = quote do:
            block:
              var `it` = `input`
              `op`
        else:
          val = input
        if defs[1].len > 1:
          op := defs[1][1]
          it := ident"it"
          ids.add(quote do:
            block:
              var `it` = newSeqWith(`cnt`, `val`)
              `op`)
        else:
          ids.add(quote do: newSeqWith(`cnt`, `val`))
        letSect.add ids
    result.add letSect

  proc makeSeq[T, Idx](num: array[Idx, int]; init: T): auto =
    when num.len == 1:
      return newSeqWith(num[0], init)
    else:
      var tmp: array[num.len-1, int]
      for i, t in tmp.mpairs: t = num[i+1]
      return newSeqWith(num[0], makeSeq(tmp, init))

  proc parseInt1(str: string): int =
    str.parseInt - 1

# ========= utils/base.nim ========= }}}

# ========= datast/binarySearchTree/aatree.nim ========= {{{

when not declared(INCLUDE_GUARD_DATAST_BINARYTREE_AATREE_NIM):
  const INCLUDE_GUARD_DATAST_BINARYTREE_AATREE_NIM = 1

  type
    AATree* = ref object
      data: int
      level: int
      size: int
      num: int
      left: AATree
      right: AATree

  proc initAATree*(data: int): AATree =
    return AATree(data: data, level: 1, size: 1, num: 1, left: nil, right: nil)

  proc skew(self: var AATree) =
    if self == nil:
      discard
    elif self.left == nil:
      discard
    elif self.left.level == self.level:
      var L = self.left
      self.left = L.right
      L.right = self
      L.size = self.size
      self.size = self.num
      if self.left != nil:
        self.size += self.left.size
      if self.right != nil:
        self.size += self.right.size
      self = L
    else:
      discard

  proc split(self: var AATree) =
    if self == nil:
      discard
    elif self.right == nil or self.right.right == nil:
      discard
    elif self.level == self.right.right.level:
      var R = self.right
      self.right = R.left
      R.left = self
      R.level.inc
      R.size = self.size
      self.size = self.num
      if self.left != nil:
        self.size += self.left.size
      if self.right != nil:
        self.size += self.right.size
      self = R
    else:
      discard

  proc insert*(self: var AATree; data: int) =
    if self == nil:
      self = initAATree(data)
      return
    elif data == self.data:
      self.size.inc
      self.num.inc
      return
    elif data < self.data:
      self.size.inc
      if self.left != nil:
        self.left.insert(data)
      else:
        self.left = initAATree(data)
    elif data > self.data:
      self.size.inc
      if self.right != nil:
        self.right.insert(data)
      else:
        self.right = initAATree(data)
    self.skew
    self.split

  proc min*(self: AATree): int =
    var node = self
    while node.left != nil: node = node.left
    return node.data

  proc max*(self: AATree): int =
    var node = self
    while node.right != nil: node = node.right
    return node.data

  proc delete*(self: var AATree; data: int): int {.discardable.} =
    # * 未検証 動作保証なし
    if self != nil:
      if self.data == data:
        result = self.num
        if self.left == nil:
          self = self.right
          return
        elif self.right == nil:
          self = self.left
          return
        else:
          var node = self.right
          while node.left != nil: node = node.left
          self.data = node.data
          self.size -= self.num
          self.num = node.num
          self.right.delete(self.data)
      elif data < self.data:
        result = self.left.delete(data)
        self.size -= result
      else:
        result = self.right.delete(data)
        self.size -= result
      if (self.left != nil and self.left.level + 1 < self.level) or (
          self.right != nil and self.right.level + 1 < self.level):
        self.level.dec
        if self.right != nil and self.right.level >
            self.level: self.right.level = self.level
        self.skew
        self.right.skew
        if self.right != nil:
          self.right.right.skew
        self.split
        self.right.split

  proc exists*(self: AATree; data: int): bool =
    if self == nil: return false
    elif data == self.data: return true
    elif data < self.data: return self.left.exists(data)
    else: return self.right.exists(data)

  proc numberOf*(self: AATree; data: int): int =
    if self == nil: return 0
    elif data == self.data: return self.num
    elif data < self.data: return self.left.numberOf(data)
    else: return self.right.numberOf(data)

  proc at*(self: AATree; pos: int): int =
    if (self.left == nil and pos < self.num) or (self.left != nil and
        self.left.size <= pos and pos < self.left.size + self.num):
      return self.data
    elif self.left != nil and self.left.size > pos:
      return self.left.at(pos)
    else:
      if self.left == nil:
        return self.right.at(pos - self.num)
      else:
        return self.right.at(pos - self.left.size - self.num)

  proc sum*(self: AATree): int =
    result = self.data * self.num
    if self.right != nil:
      result += self.right.sum
    if self.left != nil:
      result += self.left.sum

  proc takeMax*(self: AATree; x: int): int =
    if x <= 0: return 0
    if x == self.size: return self.sum
    assert(self.size >= x)
    let tmp = (if self.right == nil: 0 else: self.right.size)
    if tmp >= x:
      return self.right.takeMax(x)
    if self.right != nil:
      result = self.right.sum
    result += self.data * min(x - tmp, self.num)
    if self.left != nil:
      result += self.left.takeMax(x - tmp - self.num)

# ========= datast/binarySearchTree/aatree.nim ========= }}}

# ========= segt/segt.nim ========= {{{

when not declared(INCLUDE_GUARD_SEGT_SEGT_NIM):
  const INCLUDE_GUARD_SEGT_SEGT_NIM = 1

  import sequtils

  when (not (NimMajor <= 0)) or NimMinor >= 19:
    import sugar
  else:
    import future

  type
    SegmentTree[T] = ref object
      n: int
      node: seq[T]
      ad: (T, T) -> T
      zero: T

  proc initSegT[T](data: seq[T]; ad: (T, T) -> T; zero: T): SegmentTree[T] =
    let n = data.len
    var node = newSeq[T](2*n)
    for i in 0 ..< data.len:
      node[i+n] = data[i]
    for i in data.len ..< n:
      node[i+n] = zero
    for i in countdown(n-1, 1):
      node[i] = ad(node[2*i], node[2*i+1])
    return SegmentTree[T](n: n, node: node, ad: ad, zero: zero)

  proc initSegT[T](siz: int; ad: (T, T) -> T; zero: T): SegmentTree[T] =
    let n = siz
    var node = newSeqWith(2*n, zero)
    return SegmentTree[T](n: n, node: node, ad: ad, zero: zero)

  proc get[T](segt: SegmentTree[T]; x: int): T {.inline.} =
    segt.node[x + segt.n]

  proc update[T](segt: SegmentTree[T]; x: int; val: T) =
    var i = x + segt.n
    segt.node[i] = val
    i = i div 2
    while i > 0:
      segt.node[i] = segt.ad(segt.node[2*i], segt.node[2*i+1])
      i = i div 2

  proc applyRight[T](segt: SegmentTree[T]; x: int; val: T) {.inline.} =
    segt.update(x, segt.add(segt.get(x), val))

  proc applyLeft[T](segt: SegmentTree[T]; x: int; val: T) {.inline.} =
    segt.update(x, segt.add(val, segt.get(x)))

  proc query[T](segt: SegmentTree[T]; a, b: int): T =
    if segt.n <= a or b <= 0: return segt.zero
    var
      (l, r) = (max(segt.n, a+segt.n), min(b+segt.n, segt.n * 2))
      leftVal, rightVal = segt.zero
    while l < r:
      if l mod 2 == 1:
        leftVal = segt.ad(leftVal, segt.node[l])
        l.inc
      if r mod 2 == 1:
        r.dec
        rightVal = segt.ad(segt.node[r], rightVal)
      l = l shr 1
      r = r shr 1
    return segt.ad(leftVal, rightVal)

  # proc binarySearch[T](segt: SegmentTree[T]; )

# ========= segt/segt.nim ========= }}}

input:
  (N, Q): int
  A: seq[int]

var
  nanachi = initAATree(0)

for i in 1..N:
  nanachi.insert(i)

var
  segt = initSegT[int](
    A,
    (x: int, y: int) => x + y,
    0
  )

for q in range(Q):
  input:
    (T, l, r): (int, int1, int)
  if T == 1:
    for i in range(l+1, r):
      nanachi.delete(nanachi.at(l+1))
  else:
    echo segt.query(nanachi.at(l), nanachi.at(r))