結果
| 問題 | No.1074 増殖 |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-08-01 22:39:03 |
| 言語 | TypeScript (5.4.3) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 21,902 bytes |
| コンパイル時間 | 6,339 ms |
| コンパイル使用メモリ | 149,752 KB |
| 最終ジャッジ日時 | 2024-11-15 04:35:27 |
| 合計ジャッジ時間 | 6,972 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.ts(810,23): error TS2307: Cannot find module 'fs' or its corresponding type declarations. main.ts(811,27): error TS2307: Cannot find module 'path' or its corresponding type declarations. main.ts(816,38): error TS2304: Cannot find name '__dirname'. main.ts(818,30): error TS2580: Cannot find name 'process'. Do you need to install type definitions for node? Try `npm i --save-dev @types/node`.
ソースコード
const INF = 2e15
/**
* !`包含原点的`矩形合并/矩形面积并.
*/
class UnionRectangleRange {
private readonly _ur = new UnionRectangle()
private readonly _ul = new UnionRectangle()
private readonly _dr = new UnionRectangle()
private readonly _dl = new UnionRectangle()
/**
* 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 UnionRectangle {
sum = 0
private readonly _sl = new SortedListFast(
[
[0, INF],
[INF, 0]
],
(a, b) => a[0] - b[0]
)
/**
* Add [0, x] * [0, y].
* x >= 0.
* y >= 0.
*/
add(x: number, y: number): void {
let pos = this._sl.bisectLeft([x, -INF])
const item = this._sl.at(pos)!
if (item[1] >= y) return
const nextY = item[1]
pos--
let pre = this._sl.at(pos)!
while (pre[1] <= y) {
const x1 = pre[0]
const y1 = pre[1]
this._sl.pop(pos)
pos--
pre = this._sl.at(pos)!
this.sum -= (x1 - pre[0]) * (y1 - nextY)
}
this.sum += (x - this._sl.at(pos)![0]) * (y - nextY)
pos = this._sl.bisectLeft([x, -INF])
if (this._sl.at(pos)![0] === x) this._sl.pop(pos)
this._sl.add([x, 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 UnionRectangleRange()
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
}