const INF = 2e15 /** * A fast SortedList with O(sqrt(n)) insertion and deletion. * * @_see {@link https://github.com/981377660LMT/algorithm-study/blob/master/22_%E4%B8%93%E9%A2%98/%E7%A6%BB%E7%BA%BF%E6%9F%A5%E8%AF%A2/%E6%A0%B9%E5%8F%B7%E5%88%86%E6%B2%BB/SortedList/SortedList.ts} * @_see {@link https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py} * @_see {@link https://qiita.com/tatyam/items/492c70ac4c955c055602} * @_see {@link https://speakerdeck.com/tatyam_prime/python-dezui-qiang-falseping-heng-er-fen-tan-suo-mu-wozuo-ru} */ class SortedList { /** Optimized for 1e5 elements in javascript. Do not change it. */ protected static readonly _BLOCK_RATIO = 50 protected static readonly _REBUILD_RATIO = 170 protected readonly _compareFn: (a: T, b: T) => number protected _size: number protected _blocks: T[][] constructor() constructor(iterable: Iterable) constructor(compareFn: (a: T, b: T) => number) constructor(iterable: Iterable, compareFn: (a: T, b: T) => number) constructor(compareFn: (a: T, b: T) => number, iterable: Iterable) constructor( arg1?: Iterable | ((a: T, b: T) => number), arg2?: Iterable | ((a: T, b: T) => number) ) { let defaultCompareFn = (a: T, b: T) => (a as unknown as number) - (b as unknown as number) let defaultData: T[] = [] 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._compareFn = defaultCompareFn defaultData.sort(defaultCompareFn) this._blocks = this._initBlocks(defaultData) this._size = defaultData.length } add(value: T): void { if (!this._size) { this._blocks = [[value]] this._size = 1 return } const blockIndex = this._findBlockIndex(value) if (blockIndex === -1) { this._blocks[this._blocks.length - 1].push(value) this._size++ if ( this._blocks[this._blocks.length - 1].length > this._blocks.length * SortedList._REBUILD_RATIO ) { this._rebuild() } return } const block = this._blocks[blockIndex] const pos = this._bisectRight(block, value) block.splice(pos, 0, value) this._size += 1 if (block.length > this._blocks.length * SortedList._REBUILD_RATIO) { this._rebuild() } } /** 注意内部使用 `===` 来比较两个对象是否相等 */ has(value: T): boolean { if (!this._size) return false const blockIndex = this._findBlockIndex(value) if (blockIndex === void 0) return false const block = this._blocks[blockIndex] const pos = this._bisectLeft(block, value) return pos < block.length && value === block[pos] } /** 注意内部使用 `===` 来比较两个对象是否相等 */ discard(value: T): boolean { if (!this._size) return false const blockIndex = this._findBlockIndex(value) if (blockIndex === -1) return false const block = this._blocks[blockIndex] const pos = this._bisectLeft(block, value) if (pos === block.length || block[pos] !== value) { return false } block.splice(pos, 1) this._size -= 1 if (!block.length) { this._blocks.splice(blockIndex, 1) // !Splice When Empty, Do Not Rebuild } return true } pop(index = -1): T | undefined { if (index < 0) index += this._size if (index < 0 || index >= this._size) { return void 0 } for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (index < block.length) { const res = block[index] block.splice(index, 1) this._size -= 1 if (!block.length) { this._blocks.splice(i, 1) // !Splice When Empty, Do Not Rebuild } return res } index -= block.length } return void 0 } /** * 删除区间 [start, end) 内的元素. */ erase(start: number, end: number): void { if (start < 0) start = 0 if (end > this._size) end = this._size if (start >= end) return let [bid, startPos] = this._moveTo(start) let deleteCount = end - start for (; bid < this._blocks.length && deleteCount > 0; bid++) { const block = this._blocks[bid] const endPos = Math.min(block.length, startPos + deleteCount) const curDeleteCount = endPos - startPos if (curDeleteCount === block.length) { this._blocks.splice(bid, 1) bid-- } else { block.splice(startPos, curDeleteCount) } deleteCount -= curDeleteCount this._size -= curDeleteCount startPos = 0 } } at(index: number): T | undefined { if (index < 0) index += this._size if (index < 0 || index >= this._size) { return void 0 } for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (index < block.length) { return block[index] } index -= block.length } return void 0 } lower(value: T): T | undefined { for (let i = this._blocks.length - 1; ~i; i--) { const block = this._blocks[i] if (this._compareFn(block[0], value) < 0) { const pos = this._bisectLeft(block, value) return block[pos - 1] } } return void 0 } higher(value: T): T | undefined { for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (this._compareFn(block[block.length - 1], value) > 0) { const pos = this._bisectRight(block, value) return block[pos] } } return void 0 } floor(value: T): T | undefined { for (let i = this._blocks.length - 1; ~i; i--) { const block = this._blocks[i] if (this._compareFn(block[0], value) <= 0) { const pos = this._bisectRight(block, value) return block[pos - 1] } } return void 0 } ceiling(value: T): T | undefined { for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (this._compareFn(block[block.length - 1], value) >= 0) { const pos = this._bisectLeft(block, value) return block[pos] } } return void 0 } /** * Count the number of elements < value or * returns the index of the first element >= value. */ bisectLeft(value: T): number { let res = 0 for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (this._compareFn(value, block[block.length - 1]) <= 0) { return res + this._bisectLeft(block, value) } res += block.length } return res } /** * Count the number of elements <= value or * returns the index of the first element > value. */ bisectRight(value: T): number { let res = 0 for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (this._compareFn(value, block[block.length - 1]) < 0) { return res + this._bisectRight(block, value) } res += block.length } return res } slice(start: number, end: number): T[] { if (start < 0) start = 0 if (end > this._size) end = this._size if (start >= end) return [] let count = end - start const res: T[] = Array(count).fill(0) let [bid, startPos] = this._moveTo(start) let ptr = 0 for (; bid < this._blocks.length && count > 0; bid++) { const block = this._blocks[bid] const endPos = Math.min(block.length, startPos + count) const curCount = endPos - startPos for (let j = startPos; j < endPos; j++) { res[ptr++] = block[j] } count -= curCount startPos = 0 } return res } clear(): void { this._blocks = [] this._size = 0 } toString(): string { return `SortedList[${[...this].join(', ')}]` } /** * 返回一个迭代器,用于遍历区间 [start, end) 内的元素. */ *islice(start: number, end: number): IterableIterator { if (start < 0) start = 0 if (end > this._size) end = this._size if (start >= end) return let count = end - start let [bid, startPos] = this._moveTo(start) for (; bid < this._blocks.length && count > 0; bid++) { const block = this._blocks[bid] const endPos = Math.min(block.length, startPos + count) const curCount = endPos - startPos for (let j = startPos; j < endPos; j++) { yield block[j] } count -= curCount startPos = 0 } } /** * 返回一个迭代器,用于遍历范围在 `[min, max] 闭区间`内的元素. */ *irange(min: T, max: T): IterableIterator { const bi = this._findBlockIndex(min) for (let i = bi; 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 } } } } enumerate(start: number, end: number, f: (value: T) => void, erase = false): void { let [bid, startPos] = this._moveTo(start) let count = end - start for (; bid < this._blocks.length && count > 0; bid++) { const block = this._blocks[bid] const endPos = Math.min(block.length, startPos + count) for (let j = startPos; j < endPos; j++) { f(block[j]) } const curDeleteCount = endPos - startPos if (erase) { if (curDeleteCount === block.length) { this._blocks.splice(bid, 1) bid-- } else { block.splice(startPos, curDeleteCount) } this._size -= curDeleteCount } count -= curDeleteCount startPos = 0 } } forEach(callbackfn: (value: T, index: number) => void): void { let pos = 0 for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] for (let j = 0; j < block.length; j++) { callbackfn(block[j], pos++) } } } *entries(): IterableIterator<[number, T]> { let pos = 0 for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] for (let j = 0; j < block.length; j++) { yield [pos++, block[j]] } } } *[Symbol.iterator](): Iterator { 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] } } } // Find the block which should contain x. Block must not be empty. private _findBlockIndex(x: T): number { for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (this._compareFn(x, block[block.length - 1]) <= 0) { return i } } return -1 } private _rebuild(): void { if (!this._size) { return } const bCount = Math.ceil(Math.sqrt(this._size / SortedList._BLOCK_RATIO)) const bSize = ~~((this._size + bCount - 1) / bCount) // ceil const newB: T[][] = Array(bCount).fill(0) for (let i = 0; i < bCount; i++) { newB[i] = [] } let ptr = 0 for (let i = 0; i < this._blocks.length; i++) { const b = this._blocks[i] for (let j = 0; j < b.length; j++) { newB[~~(ptr / bSize)].push(b[j]) ptr++ } } this._blocks = newB } // eslint-disable-next-line class-methods-use-this private _initBlocks(sorted: T[]): T[][] { const bCount = Math.ceil(Math.sqrt(sorted.length / SortedList._BLOCK_RATIO)) const bSize = ~~((sorted.length + bCount - 1) / bCount) // ceil const newB: T[][] = Array(bCount).fill(0) for (let i = 0; i < bCount; i++) { newB[i] = [] } for (let i = 0; i < bCount; i++) { for (let j = i * bSize; j < Math.min((i + 1) * bSize, sorted.length); j++) { newB[i].push(sorted[j]) } } return newB } private _bisectLeft(nums: T[], value: T): number { let left = 0 let right = nums.length - 1 while (left <= right) { const mid = (left + right) >> 1 if (this._compareFn(value, nums[mid]) <= 0) { right = mid - 1 } else { left = mid + 1 } } return left } private _bisectRight(nums: T[], value: T): number { let left = 0 let right = nums.length - 1 while (left <= right) { const mid = (left + right) >> 1 if (this._compareFn(value, nums[mid]) < 0) { right = mid - 1 } else { left = mid + 1 } } return left } private _moveTo(index: number): [blockId: number, startPos: number] { for (let i = 0; i < this._blocks.length; i++) { const block = this._blocks[i] if (index < block.length) { return [i, index] } index -= block.length } return [this._blocks.length, 0] } get length(): number { return this._size } } /** * !`包含原点的`矩形合并/矩形面积并. */ 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 SortedList( [ [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 } } 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 }