#880745 (TypeScript) No.789 範囲の合計

提出ソース
結果

問題	No.789 範囲の合計
ユーザー	草苺奶昔
提出日時	2023-06-14 23:32:38
言語	TypeScript (5.4.3)
結果	WA
実行時間	-
コード長	12,003 bytes
コンパイル時間	7,353 ms
コンパイル使用メモリ	259,992 KB
実行使用メモリ	77,440 KB
最終ジャッジ日時	2023-09-05 08:40:40
合計ジャッジ時間	15,166 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	82 ms 42,064 KB
testcase_01	AC	80 ms 42,028 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	80 ms 42,060 KB
testcase_14	AC	83 ms 44,164 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
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 static _isPrimitive(
    o: unknown
  ): o is number | string | boolean | symbol | bigint | null | undefined {
    return o === null || (typeof o !== 'object' && typeof o !== 'function')
  }

  private readonly _lower: number
  private readonly _upper: number
  private readonly _e: () => E
  private readonly _op: (a: E, b: E) => E
  private readonly _persistent: boolean
  private _root: SegNode<E>

  /**
   * 单点修改区间查询的动态开点懒标记线段树.线段树维护的值域为`[start, end)`.
   * @param start 值域下界.start>=0.
   * @param end 值域上界.
   * @param e 幺元.
   * @param op 结合律的二元操作.
   * @param persistent 是否持久化.持久化后,每次修改都会新建一个结点,否则会复用原来的结点.
   */
  constructor(start: number, end: number, e: () => E, op: (a: E, b: E) => E, persistent = false) {
    if (persistent && !SegmentTreeDynamic._isPrimitive(e())) {
      throw new Error('persistent is only supported when e() return primitive values')
    }
    this._lower = start
    this._upper = end + 5
    this._e = e
    this._op = op
    this._persistent = persistent
    this._root = this.newRoot()
  }

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

  get(index: number, root: SegNode<E> = this._root): E {
    if (index < this._lower || index >= this._upper) return this._e()
    return this._get(root, index)
  }

  set(index: number, value: E, root: SegNode<E> = this._root): SegNode<E> {
    if (index < this._lower || index >= this._upper) return root
    const newRoot = this._set(root, this._lower, this._upper, index, value)
    this._root = newRoot
    return newRoot
  }

  update(index: number, value: E, root: SegNode<E> = this._root): SegNode<E> {
    if (index < this._lower || index >= this._upper) return root
    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 {
    if (start < this._lower) start = this._lower
    if (end > this._upper) end = this._upper
    if (start >= end) return this._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
  }

  queryAll(root: SegNode<E> = this._root): E {
    return root.sum
  }

  /**
   * 二分查询最大的`end`使得切片`[start:end)`内的聚合值满足`check`.
   * {@link _lower} <= start <= {@link _upper}.
   * @alias findFirst
   */
  maxRight(start: number, check: (e: E) => boolean, root: SegNode<E> = this._root): number {
    if (start < this._lower) start = this._lower
    if (start >= this._upper) return this._upper

    let x = this._e()
    const _maxRight = (node: SegNode<E> | undefined, l: number, r: number, ql: number): number => {
      if (!node || r <= ql) return this._upper
      const tmp = this._op(x, node.sum)
      if (check(tmp)) {
        x = tmp
        return this._upper
      }
      const m = Math.floor(l + (r - l) / 2)
      const k = _maxRight(node.left, l, m, ql)
      if (k !== this._upper) return k
      if (ql <= node.index) {
        x = this._op(x, node.data)
        if (!check(x)) {
          return node.index
        }
      }
      return _maxRight(node.right, m, r, ql)
    }

    return _maxRight(root, this._lower, this._upper, start)
  }

  /**
   * 二分查询最小的`start`使得切片`[start:end)`内的聚合值满足`check`.
   * {@link _lower} <= end <= {@link _upper}.
   * @alias findLast
   */
  minLeft(end: number, check: (e: E) => boolean, root: SegNode<E> = this._root): number {
    if (end > this._upper) end = this._upper
    if (end <= this._lower) return this._lower

    let x = this._e()
    const _minLeft = (node: SegNode<E> | undefined, l: number, r: number, qr: number): number => {
      if (!node || qr <= l) return this._lower
      const tmp = this._op(node.sum, x)
      if (check(tmp)) {
        x = tmp
        return this._lower
      }
      const m = Math.floor(l + (r - l) / 2)
      const k = _minLeft(node.right, m, r, qr)
      if (k !== this._lower) return k
      if (node.index < qr) {
        x = this._op(node.data, x)
        if (!check(x)) {
          return node.index + 1
        }
      }
      return _minLeft(node.left, l, m, qr)
    }

    return _minLeft(root, this._lower, this._upper, end)
  }

  getAll(root: SegNode<E> = this._root): [index: number, value: E][] {
    const res: [number, E][] = []
    const _getAll = (node: SegNode<E> | undefined) => {
      if (!node) return
      _getAll(node.left)
      res.push([node.index, node.data])
      _getAll(node.right)
    }
    _getAll(root)
    return res
  }

  private _copyNode(node: SegNode<E>): SegNode<E> {
    if (!node || !this._persistent) return node
    return { left: node.left, right: node.right, index: node.index, data: node.data, sum: node.sum }
  }

  private _get(root: SegNode<E> | undefined, index: number): E {
    if (!root) return this._e()
    if (index === root.index) return root.data
    if (index < root.index) return this._get(root.left, index)
    return this._get(root.right, index)
  }

  private _set(root: SegNode<E> | undefined, l: number, r: number, i: number, x: E): SegNode<E> {
    if (!root) return SegmentTreeDynamic._newNode(i, x)
    root = this._copyNode(root)
    if (root.index === i) {
      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._set(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._set(root.right, m, r, i, x)
    }
    this._pushUp(root)
    return root
  }

  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)
    root = this._copyNode(root)
    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
    }
  }
}
// /**
//  * !不要用数组`[]`代替对象`{}`.数组会导致性能下降.
//  */
// 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) => {
//       ql = l > ql ? l : ql
//       qr = r < qr ? r : qr
//       if (ql >= qr || !node) return
//       if (l === ql && r === qr) {
//         res = this._op(res, root.sum)
//         return
//       }
//       const m = (l + r) >>> 1
//       _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) {
//       root = SegmentTreeDynamic._newNode(i, x)
//       return root
//     }

//     if (root.index === i) {
//       root.data = this._op(root.data, x)
//       this._pushUp(root)
//       return root
//     }
//     const m = (l + r) >>> 1
//     if (i < m) {
//       if (root.index < i) {
//         ;[root.index, i] = [i, root.index]
//         ;[root.data, x] = [x, root.data]
//       }
//       root.left = this._update(root.left, l, m, i, x)
//     } else {
//       if (i < root.index) {
//         ;[root.index, i] = [i, root.index]
//         ;[root.data, x] = [x, root.data]
//       }
//       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
)

const n = Number(input())
let res = 0
for (let i = 0; i < n; i++) {
  const arr = input().split(' ').map(Number)
  if (arr[0] === 0) {
    const pre = seg.get(arr[1])
    seg.set(arr[1], pre + arr[2])
  } else {
    res += seg.query(arr[1], arr[2] + 1)
  }
}
console.log(res)
yukicoder

結果

テストケース

ソースコード
