結果

問題 No.789 範囲の合計
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-06-14 23:15:05
言語 TypeScript
(5.4.3)
結果
WA  
実行時間 -
コード長 3,779 bytes
コンパイル時間 7,682 ms
コンパイル使用メモリ 253,872 KB
実行使用メモリ 77,432 KB
最終ジャッジ日時 2023-09-05 08:26:48
合計ジャッジ時間 14,518 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
42,412 KB
testcase_01 AC 77 ms
42,332 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 81 ms
42,232 KB
testcase_14 AC 81 ms
42,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/problems/no/789
import * as fs from 'fs'
import { resolve } from 'path'
/**
 * !不要用数组`[]`代替对象`{}`.数组会导致性能下降.
 */
type SegNode<E> = {
  left: SegNode<E> | undefined
  right: SegNode<E> | undefined
  index: number
  data: E
  sum: E
}

class SegmentTreeDynamic<E = number> {
  private readonly _lower: number
  private readonly _upper: number
  private readonly _e: () => E
  private readonly _op: (a: E, b: E) => E
  private _root: SegNode<E>

  constructor(start: number, end: number, e: () => E, op: (a: E, b: E) => E) {
    this._lower = start
    this._upper = end + 5
    this._e = e
    this._op = op
    this._root = this.newRoot()
  }

  newRoot(): SegNode<E> {
    return undefined as any // nil
  }

  update(index: number, value: E, root: SegNode<E> = this._root): SegNode<E> {
    const newRoot = this._update(root, this._lower, this._upper, index, value)
    this._root = newRoot
    return newRoot
  }

  /**
   * 查询区间`[start,end)`的聚合值.
   * {@link _lower} <= start <= end <= {@link _upper}.
   */
  query(start: number, end: number, root: SegNode<E> = this._root): E {
    let res = this._e()
    const _query = (node: SegNode<E> | undefined, l: number, r: number, ql: number, qr: number) => {
      if (!node) return
      ql = l > ql ? l : ql
      qr = r < qr ? r : qr
      if (ql >= qr) return
      if (l === ql && r === qr) {
        res = this._op(res, root.sum)
        return
      }
      const m = Math.floor(l + (r - l) / 2)
      _query(node.left, l, m, ql, qr)
      if (ql <= node.index && node.index < qr) {
        res = this._op(res, node.data)
      }
      _query(node.right, m, r, ql, qr)
    }

    _query(root, this._lower, this._upper, start, end)
    return res
  }

  private _pushUp(root: SegNode<E>): void {
    root.sum = root.data
    if (root.left) root.sum = this._op(root.left.sum, root.sum)
    if (root.right) root.sum = this._op(root.sum, root.right.sum)
  }

  private _update(root: SegNode<E> | undefined, l: number, r: number, i: number, x: E): SegNode<E> {
    if (!root) return SegmentTreeDynamic._newNode(i, x)

    if (root.index === i) {
      root.data = this._op(root.data, x)
      this._pushUp(root)
      return root
    }
    const m = Math.floor(l + (r - l) / 2)
    if (i < m) {
      if (root.index < i) {
        const tmp1 = root.index
        root.index = i
        i = tmp1
        const tmp2 = root.data
        root.data = x
        x = tmp2
      }
      root.left = this._update(root.left, l, m, i, x)
    } else {
      if (i < root.index) {
        const tmp1 = root.index
        root.index = i
        i = tmp1
        const tmp2 = root.data
        root.data = x
        x = tmp2
      }
      root.right = this._update(root.right, m, r, i, x)
    }
    this._pushUp(root)
    return root
  }

  private static _newNode<V>(index: number, value: V): SegNode<V> {
    return {
      index,
      left: undefined,
      right: undefined,
      data: value,
      sum: value
    }
  }
}

function useInput(path?: string) {
  let data: string
  if (path) {
    data = fs.readFileSync(resolve(__dirname, path), 'utf8')
  } else {
    data = fs.readFileSync(process.stdin.fd, 'utf8')
  }

  const lines = data.split(/\r\n|\r|\n/)
  let lineId = 0
  const input = (): string => lines[lineId++]

  return {
    input
  }
}

const { input } = useInput()

const seg = new SegmentTreeDynamic<number>(
  0,
  1e9 + 10,
  () => 0,
  (a, b) => a + b
)
let root = seg.newRoot()
const n = Number(input())
let res = 0
for (let i = 0; i < n; i++) {
  const arr = input().split(' ').map(Number)
  if (arr[0] === 0) {
    root = seg.update(arr[1], arr[2], root)
  } else {
    res += seg.query(arr[1], arr[2] + 1, root)
  }
}
console.log(res)
0