結果

問題 No.1074 増殖
ユーザー 草苺奶昔
提出日時 2023-10-14 13:20:06
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 914 ms / 2,000 ms
コード長 22,073 bytes
コンパイル時間 8,063 ms
コンパイル使用メモリ 232,256 KB
実行使用メモリ 60,964 KB
最終ジャッジ日時 2024-12-31 17:02:17
合計ジャッジ時間 16,580 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

const INF = 2e9
/**
 * !`包含原点的`矩形合并/矩形面积并.
 */
class IncrementalRectangleUnionRange {
  private readonly _ur = new IncrementalRectangleUnion()
  private readonly _ul = new IncrementalRectangleUnion()
  private readonly _dr = new IncrementalRectangleUnion()
  private readonly _dl = new IncrementalRectangleUnion()
  /**
   * Add [x1, x2] * [y1, y2].
   * x1 <= 0 <= x2.
   * y1 <= 0 <= y2.
   */
  add(x1: number, x2: number, y1: number, y2: number): void {
    this._ur.add(x2, y2)
    this._ul.add(-x1, y2)
    this._dr.add(x2, -y1)
    this._dl.add(-x1, -y1)
  }
  query(): number {
    return this._ur.sum + this._ul.sum + this._dr.sum + this._dl.sum
  }
}
/**
 * !`包含原点的`矩形合并/矩形面积并.
 */
class IncrementalRectangleUnion {
  sum = 0
  private readonly _sl = new SortedListFast(
    [
      { start: 0, end: INF },
      { start: INF, end: 0 }
    ],
    (a, b) => a.start - b.start
  )
  /**
   * Add [0, x] * [0, y].
   * x >= 0.
   * y >= 0.
   */
  add(x: number, y: number): void {
    let pos = this._sl.bisectLeft({ start: x, end: -INF })
    const item = this._sl.at(pos)!
    if (item.end >= y) return
    const nextY = item.end
    pos--
    let pre = this._sl.at(pos)!
    while (pre.end <= y) {
      const x1 = pre.start
      const y1 = pre.end
      this._sl.pop(pos)
      pos--
      pre = this._sl.at(pos)!
      this.sum -= (x1 - pre.start) * (y1 - nextY)
    }
    this.sum += (x - this._sl.at(pos)!.start) * (y - nextY)
    pos = this._sl.bisectLeft({ start: x, end: -INF })
    if (this._sl.at(pos)!.start === x) this._sl.pop(pos)
    this._sl.add({ start: x, end: y })
  }
  query(): number {
    return this.sum
  }
}
// API.
interface ISortedList<V> {
  add(value: V): void
  has(value: V, equals?: (a: V, b: V) => boolean): boolean
  discard(value: V, equals?: (a: V, b: V) => boolean): boolean
  pop(index?: number): V | undefined
  at(index: number): V | undefined
  erase(start?: number, end?: number): void
  lower(value: V): V | undefined
  higher(value: V): V | undefined
  floor(value: V): V | undefined
  ceiling(value: V): V | undefined
  bisectLeft(value: V): number
  bisectRight(value: V): number
  count(value: V): number
  slice(start?: number, end?: number): V[]
  clear(): void
  update(...values: V[]): void
  merge(other: ISortedList<V>): void
  toString(): string
  forEach(callbackfn: (value: V, index: number) => void | boolean, reverse?: boolean): void
  enumerate(start: number, end: number, f: (value: V) => void, erase?: boolean): void
  iSlice(start: number, end: number, reverse?: boolean): IterableIterator<V>
  iRange(min: V, max: V, reverse?: boolean): IterableIterator<V>
  entries(): IterableIterator<[number, V]>
  [Symbol.iterator](): IterableIterator<V>
  iteratorAt(index: number): ISortedListIterator<V>
  lowerBound(value: V): ISortedListIterator<V>
  upperBound(value: V): ISortedListIterator<V>
  readonly length: number
  readonly min: V | undefined
  readonly max: V | undefined
}
interface ISortedListIterator<V> {
  hasNext(): boolean
  next(): V | undefined
  hasPrev(): boolean
  prev(): V | undefined
  remove(): void
  readonly value: V | undefined
}
/**
 * 使用分块+树状数组维护的有序序列.
 * !如果数组较短(<2000),直接使用`bisectInsort`维护即可.
 */
class SortedListFast<V = number> {
  static setLoadFactor(load = 500): void {
    this._LOAD = load
  }
  /**
   * 负载因子，用于控制每个块的长度.
   * 长度为`1e5`的数组, 负载因子取`500`左右性能较好.
   */
  protected static _LOAD = 500
  private static _isPrimitive(
    o: unknown
  ): o is number | string | boolean | symbol | bigint | null | undefined {
    return o === null || (typeof o !== 'object' && typeof o !== 'function')
  }
  protected _compareFn!: (a: V, b: V) => number
  protected _len!: number
  /**
   * 各个块.
   */
  protected _blocks!: V[][]
  /**
   * 各个块的最小值.
   */
  protected _mins!: V[]
  /**
   * 树状数组维护各个块长度的前缀和，便于根据索引定位到对应的元素.
   */
  protected _tree!: number[]
  protected _shouldRebuildTree!: boolean
  constructor()
  constructor(iterable: Iterable<V>)
  constructor(compareFn: (a: V, b: V) => number)
  constructor(iterable: Iterable<V>, compareFn: (a: V, b: V) => number)
  constructor(compareFn: (a: V, b: V) => number, iterable: Iterable<V>)
  constructor(
    arg1?: Iterable<V> | ((a: V, b: V) => number),
    arg2?: Iterable<V> | ((a: V, b: V) => number)
  ) {
    let defaultCompareFn = (a: V, b: V) => (a as unknown as number) - (b as unknown as number)
    let defaultData: V[] = []
    if (arg1 !== void 0) {
      if (typeof arg1 === 'function') {
        defaultCompareFn = arg1
      } else {
        defaultData = [...arg1]
      }
    }
    if (arg2 !== void 0) {
      if (typeof arg2 === 'function') {
        defaultCompareFn = arg2
      } else {
        defaultData = [...arg2]
      }
    }
    this._build(defaultData, defaultCompareFn)
  }
  add(value: V): this {
    const { _blocks, _mins } = this
    this._len++
    if (!_blocks.length) {
      _blocks.push([value])
      _mins.push(value)
      this._shouldRebuildTree = true
      return this
    }
    const load = SortedListFast._LOAD
    const pair = this._locRight(value)
    const pos = pair[0]
    const index = pair[1]
    this._updateTree(pos, 1)
    const block = _blocks[pos]
    block.splice(index, 0, value)
    _mins[pos] = block[0]
    // !-> [x]*load + [x]*(block.length - load)
    if (load + load < block.length) {
      _blocks.splice(pos + 1, 0, block.slice(load))
      _mins.splice(pos + 1, 0, block[load])
      block.splice(load)
      this._shouldRebuildTree = true
    }
    return this
  }
  update(...values: V[]): this {
    const n = values.length
    if (n < this._len << 2) {
      for (let i = 0; i < n; i++) this.add(values[i])
      return this
    }
    const data = Array(this._len + n)
    let ptr = 0
    this.forEach(v => {
      data[ptr++] = v
    })
    for (let i = 0; i < n; i++) data[ptr++] = values[i]
    this._build(data, this._compareFn)
    return this
  }
  merge(other: SortedListFast<V>): this {
    const n = other.length
    if (n < this._len << 2) {
      other.forEach(v => {
        this.add(v)
      })
      return this
    }
    const data = Array(this._len + n)
    let ptr = 0
    this.forEach(v => {
      data[ptr++] = v
    })
    other.forEach(v => {
      data[ptr++] = v
    })
    this._build(data, this._compareFn)
    return this
  }
  has(value: V, equals?: (a: V, b: V) => boolean): boolean {
    if (!equals && !SortedListFast._isPrimitive(value)) {
      throw new Error('equals must be provided when value is a non-primitive value')
    }
    const block = this._blocks
    if (!block.length) return false
    equals = equals || ((a: V, b: V) => a === b)
    const pair = this._locLeft(value)
    const pos = pair[0]
    const index = pair[1]
    return index < block[pos].length && equals(block[pos][index], value)
  }
  discard(value: V, equals?: (a: V, b: V) => boolean): boolean {
    if (!equals && !SortedListFast._isPrimitive(value)) {
      throw new Error('equals must be provided when value is a non-primitive value')
    }
    const block = this._blocks
    if (!block.length) return false
    equals = equals || ((a: V, b: V) => a === b)
    const pair = this._locRight(value)
    const pos = pair[0]
    const index = pair[1]
    if (index && equals(block[pos][index - 1], value)) {
      this._delete(pos, index - 1)
      return true
    }
    return false
  }
  pop(index = -1): V | undefined {
    if (index < 0) index += this._len
    if (index < 0 || index >= this._len) return void 0
    const pair = this._findKth(index)
    const pos = pair[0]
    const index_ = pair[1]
    const value = this._blocks[pos][index_]
    this._delete(pos, index_)
    return value
  }
  at(index: number): V | undefined {
    if (index < 0) index += this._len
    if (index < 0 || index >= this._len) return void 0
    const pair = this._findKth(index)
    const pos = pair[0]
    const index_ = pair[1]
    return this._blocks[pos][index_]
  }
  /**
   * 删除区间 `[start, end)` 内的元素.
   */
  erase(start = 0, end = this.length): void {
    // eslint-disable-next-line @typescript-eslint/no-empty-function
    this.enumerate(start, end, () => {}, true)
  }
  lower(value: V): V | undefined {
    const pos = this.bisectLeft(value)
    return pos ? this.at(pos - 1) : void 0
  }
  higher(value: V): V | undefined {
    const pos = this.bisectRight(value)
    return pos < this._len ? this.at(pos) : void 0
  }
  floor(value: V): V | undefined {
    const pos = this.bisectRight(value)
    return pos ? this.at(pos - 1) : void 0
  }
  ceiling(value: V): V | undefined {
    const pos = this.bisectLeft(value)
    return pos < this._len ? this.at(pos) : void 0
  }
  /**
   * 返回第一个大于等于 `value` 的元素的索引/严格小于 `value` 的元素的个数.
   */
  bisectLeft(value: V): number {
    const pair = this._locLeft(value)
    const pos = pair[0]
    const index = pair[1]
    return this._queryTree(pos) + index
  }
  /**
   * 返回第一个严格大于 `value` 的元素的索引/小于等于 `value` 的元素的个数.
   */
  bisectRight(value: V): number {
    const pair = this._locRight(value)
    const pos = pair[0]
    const index = pair[1]
    return this._queryTree(pos) + index
  }
  count(value: V): number {
    return this.bisectRight(value) - this.bisectLeft(value)
  }
  slice(start = 0, end = this.length): V[] {
    if (start < 0) start += this._len
    if (start < 0) start = 0
    if (end < 0) end += this._len
    if (end > this._len) end = this._len
    if (start >= end) return []
    const res = Array(end - start)
    let count = 0
    this.enumerate(
      start,
      end,
      value => {
        res[count++] = value
      },
      false
    )
    return res
  }
  clear(): void {
    this._len = 0
    this._blocks = []
    this._mins = []
    this._tree = []
    this._shouldRebuildTree = true
  }
  toString(): string {
    const res = Array(this._len)
    this.forEach((value, index) => {
      res[index] = value
    })
    return `SortedList{${res.join(',')}}`
  }
  /**
   * @param callbackfn 回调函数, 返回 `true` 时终止遍历.
   * @param reverse 是否逆序遍历.
   */
  forEach(callbackfn: (value: V, index: number) => void | boolean, reverse = false): void {
    if (!reverse) {
      let count = 0
      for (let i = 0; i < this._blocks.length; i++) {
        const block = this._blocks[i]
        for (let j = 0; j < block.length; j++) {
          if (callbackfn(block[j], count++)) return
        }
      }
      return
    }
    let count = 0
    for (let i = this._blocks.length - 1; ~i; i--) {
      const block = this._blocks[i]
      for (let j = block.length - 1; ~j; j--) {
        if (callbackfn(block[j], count++)) return
      }
    }
  }
  enumerate(start: number, end: number, f: (value: V) => void, erase = false): void {
    if (start < 0) start = 0
    if (end > this._len) end = this._len
    if (start >= end) return
    const pair = this._findKth(start)
    let pos = pair[0]
    let startIndex = pair[1]
    let count = end - start
    for (; count && pos < this._blocks.length; pos++) {
      const block = this._blocks[pos]
      const endIndex = Math.min(block.length, startIndex + count)
      for (let j = startIndex; j < endIndex; j++) f(block[j])
      const deleted = endIndex - startIndex
      if (erase) {
        if (deleted === block.length) {
          // !delete block
          this._blocks.splice(pos, 1)
          this._mins.splice(pos, 1)
          this._shouldRebuildTree = true
          pos--
        } else {
          // !delete [index, end)
          for (let i = startIndex; i < endIndex; i++) this._updateTree(pos, -1)
          block.splice(startIndex, deleted)
          this._mins[pos] = block[0]
        }
        this._len -= deleted
      }
      count -= deleted
      startIndex = 0
    }
  }
  /**
   * 返回一个迭代器，用于遍历区间 `[start, end)` 内的元素.
   */
  *iSlice(start = 0, end = this.length, reverse = false): IterableIterator<V> {
    if (start < 0) start += this._len
    if (start < 0) start = 0
    if (end < 0) end += this._len
    if (end > this._len) end = this._len
    if (start >= end) return
    let count = end - start
    if (reverse) {
      let [pos, index] = this._findKth(end)
      for (; count && ~pos; pos--, ~pos && (index = this._blocks[pos].length)) {
        const block = this._blocks[pos]
        const startPos = Math.max(0, index - count)
        const curCount = index - startPos
        for (let j = index - 1; j >= startPos; j--) yield block[j]
        count -= curCount
      }
    } else {
      let [pos, index] = this._findKth(start)
      for (; count && pos < this._blocks.length; pos++) {
        const block = this._blocks[pos]
        const endPos = Math.min(block.length, index + count)
        const curCount = endPos - index
        for (let j = index; j < endPos; j++) yield block[j]
        count -= curCount
        index = 0
      }
    }
  }
  /**
   * 返回一个迭代器，用于遍历范围在 `[min, max] 闭区间`内的元素.
   */
  *iRange(min: V, max: V, reverse = false): IterableIterator<V> {
    if (this._compareFn(min, max) > 0) return
    if (reverse) {
      let pos = this._locBlock(max)
      for (let i = pos; ~i; i--) {
        const block = this._blocks[i]
        for (let j = block.length - 1; ~j; j--) {
          const x = block[j]
          if (this._compareFn(x, min) < 0) return
          if (this._compareFn(x, max) <= 0) yield x
        }
      }
    } else {
      const pos = this._locBlock(min)
      for (let i = pos; i < this._blocks.length; i++) {
        const block = this._blocks[i]
        for (let j = 0; j < block.length; j++) {
          const x = block[j]
          if (this._compareFn(x, max) > 0) return
          if (this._compareFn(x, min) >= 0) yield x
        }
      }
    }
  }
  *entries(): IterableIterator<[number, V]> {
    let count = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield [count++, block[j]]
      }
    }
  }
  *[Symbol.iterator](): IterableIterator<V> {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield block[j]
      }
    }
  }
  iteratorAt(index: number): ISortedListIterator<V> {
    if (index < 0) index += this._len
    if (index < 0 || index >= this._len) throw new RangeError('Index out of range')
    const pair = this._findKth(index)
    return this._iteratorAt(pair[0], pair[1])
  }
  lowerBound(value: V): ISortedListIterator<V> {
    const [pos, index] = this._locLeft(value)
    return this._iteratorAt(pos, index)
  }
  upperBound(value: V): ISortedListIterator<V> {
    const [pos, index] = this._locRight(value)
    return this._iteratorAt(pos, index)
  }
  get length(): number {
    return this._len
  }
  get min(): V | undefined {
    if (!this._len) return void 0
    return this._mins[0]
  }
  get max(): V | undefined {
    if (!this._len) return void 0
    const { _blocks } = this
    const lastBlock = _blocks[_blocks.length - 1]
    return lastBlock[lastBlock.length - 1]
  }
  protected _build(data: V[], compareFn: (a: V, b: V) => number): void {
    data.sort(compareFn)
    const n = data.length
    const blocks = []
    for (let i = 0; i < n; i += SortedListFast._LOAD) {
      blocks.push(data.slice(i, i + SortedListFast._LOAD))
    }
    const mins = Array(blocks.length)
    for (let i = 0; i < blocks.length; i++) {
      const cur = blocks[i]
      mins[i] = cur[0]
    }
    this._compareFn = compareFn
    this._len = n
    this._blocks = blocks
    this._mins = mins
    this._tree = []
    this._shouldRebuildTree = true
  }
  protected _delete(pos: number, index: number): void {
    const { _blocks, _mins } = this
    // !delete element
    this._len--
    this._updateTree(pos, -1)
    const block = _blocks[pos]
    block.splice(index, 1)
    if (block.length) {
      _mins[pos] = block[0]
      return
    }
    // !delete block
    _blocks.splice(pos, 1)
    _mins.splice(pos, 1)
    this._shouldRebuildTree = true
  }
  protected _locLeft(value: V): [pos: number, index: number] {
    if (!this._len) return [0, 0]
    const { _blocks, _mins } = this
    // find pos
    let left = -1
    let right = _blocks.length - 1
    while (left + 1 < right) {
      const mid = (left + right) >>> 1
      if (this._compareFn(value, _mins[mid]) <= 0) {
        right = mid
      } else {
        left = mid
      }
    }
    if (right) {
      const block = _blocks[right - 1]
      if (this._compareFn(value, block[block.length - 1]) <= 0) {
        right--
      }
    }
    const pos = right
    // find index
    const cur = _blocks[pos]
    left = -1
    right = cur.length
    while (left + 1 < right) {
      const mid = (left + right) >>> 1
      if (this._compareFn(value, cur[mid]) <= 0) {
        right = mid
      } else {
        left = mid
      }
    }
    return [pos, right]
  }
  protected _locRight(value: V): [pos: number, index: number] {
    if (!this._len) return [0, 0]
    const { _blocks, _mins } = this
    // find pos
    let left = 0
    let right = _blocks.length
    while (left + 1 < right) {
      const mid = (left + right) >>> 1
      if (this._compareFn(value, _mins[mid]) < 0) {
        right = mid
      } else {
        left = mid
      }
    }
    const pos = left
    // find index
    const cur = _blocks[pos]
    left = -1
    right = cur.length
    while (left + 1 < right) {
      const mid = (left + right) >>> 1
      if (this._compareFn(value, cur[mid]) < 0) {
        right = mid
      } else {
        left = mid
      }
    }
    return [pos, right]
  }
  protected _locBlock(value: V): number {
    let left = -1
    let right = this._blocks.length - 1
    while (left + 1 < right) {
      const mid = (left + right) >>> 1
      if (this._compareFn(value, this._mins[mid]) <= 0) {
        right = mid
      } else {
        left = mid
      }
    }
    if (right) {
      const block = this._blocks[right - 1]
      if (this._compareFn(value, block[block.length - 1]) <= 0) {
        right--
      }
    }
    return right
  }
  private _buildTree(): void {
    this._tree = Array(this._blocks.length)
    for (let i = 0; i < this._blocks.length; i++) {
      this._tree[i] = this._blocks[i].length
    }
    const tree = this._tree
    for (let i = 0; i < tree.length; i++) {
      const j = i | (i + 1)
      if (j < tree.length) {
        tree[j] += tree[i]
      }
    }
    this._shouldRebuildTree = false
  }
  protected _updateTree(index: number, delta: number): void {
    if (!this._shouldRebuildTree) {
      const tree = this._tree
      while (index < tree.length) {
        tree[index] += delta
        index |= index + 1
      }
    }
  }
  private _queryTree(end: number): number {
    if (this._shouldRebuildTree) this._buildTree()
    const tree = this._tree
    let x = 0
    while (end) {
      x += tree[end - 1]
      end &= end - 1
    }
    return x
  }
  /**
   * 树状数组树上二分, 找到索引为 `k` 的元素的`(所在块的索引pos, 块内的索引index)`.
   * 内部对头部块和尾部块做了特殊处理.
   */
  protected _findKth(k: number): [pos: number, index: number] {
    if (k < this._blocks[0].length) return [0, k]
    const last = this._blocks.length - 1
    const lastLen = this._blocks[last].length
    if (k >= this._len - lastLen) return [last, k + lastLen - this._len]
    if (this._shouldRebuildTree) this._buildTree()
    const tree = this._tree
    let pos = -1
    const bitLength = 32 - Math.clz32(tree.length)
    for (let d = bitLength - 1; ~d; d--) {
      const next = pos + (1 << d)
      if (next < tree.length && k >= tree[next]) {
        pos = next
        k -= tree[pos]
      }
    }
    return [pos + 1, k]
  }
  private _iteratorAt(pos: number, index: number): ISortedListIterator<V> {
    const hasNext = (): boolean => {
      return pos < this._blocks.length - 1 || index < this._blocks[pos].length - 1
    }
    const next = (): V | undefined => {
      if (!hasNext()) return void 0
      index++
      if (index === this._blocks[pos].length) {
        pos++
        index = 0
      }
      return this._blocks[pos][index]
    }
    const hasPrev = (): boolean => {
      return pos > 0 || index > 0
    }
    const prev = (): V | undefined => {
      if (!hasPrev()) return void 0
      index--
      if (index === -1) {
        pos--
        index = this._blocks[pos].length - 1
      }
      return this._blocks[pos][index]
    }
    const remove = (): void => {
      this._delete(pos, index)
    }
    // eslint-disable-next-line @typescript-eslint/no-this-alias
    const sl = this
    return {
      hasNext,
      next,
      hasPrev,
      prev,
      remove,
      get value(): V | undefined {
        if (pos < 0 || pos >= sl.length) return void 0
        const block = sl._blocks[pos]
        if (index < 0 || index >= block.length) return void 0
        return block[index]
      }
    }
  }
}
import * as fs from 'fs'
import { resolve } from 'path'
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 n = Number(input())
const R = new IncrementalRectangleUnionRange()
let pre = 0
for (let i = 0; i < n; i++) {
  const [x1, y1, x2, y2] = input().split(' ').map(Number)
  R.add(x1, x2, y1, y2)
  const cur = R.query()
  console.log(cur - pre)
  pre = cur
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0