結果
問題 | No.789 範囲の合計 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-06-14 23:13:51 |
言語 | TypeScript (5.4.3) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,691 bytes |
コンパイル時間 | 7,251 ms |
コンパイル使用メモリ | 258,616 KB |
実行使用メモリ | 76,960 KB |
最終ジャッジ日時 | 2023-09-05 08:25:52 |
合計ジャッジ時間 | 14,658 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 81 ms
42,348 KB |
testcase_01 | AC | 82 ms
42,376 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 | 79 ms
42,448 KB |
testcase_14 | AC | 78 ms
42,396 KB |
ソースコード
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 _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._root = this.newRoot() } newRoot(): SegNode<E> { return undefined as any // nil } 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 } 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)