deno.land / x / masx200_leetcode_test@10.6.5 / rectangle-area-ii / rectangleArea.ts
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163export default function rectangleArea(rectangles: number[][]): number { const down = Math.min(...rectangles.map((a) => a[1]));
const up = Math.max(...rectangles.map((a) => a[3])); const root = new SegTree(down, up); const sweep = new Map<number, [number, number, number][]>(); for (const [left, down, right, up] of rectangles) { insert(sweep, left, down, up, 1); insert(sweep, right, down, up, -1); } // for (const arr of sweep.values()) { // arr.sort((a, b) => { // if (a[0] != b[0]) { // return a[0] - b[0]; // } else if (a[1] != b[1]) { // return a[1] - b[1]; // } else { // return a[2] - b[2]; // } // }); // } let ans = 0n; const sorted = [...sweep.entries()].sort((a, b) => a[0] - b[0]); for (const [index, [key, arr]] of sorted.entries()) { if (index === sorted.length - 1) break; for (const [down, up, diff] of arr) { update( root, { left: down, right: up }, { modify: (node) => { node.count += diff;
node.value = Math.sign(node.count) * (node.right - node.left); }, create: ({ left, right }) => new SegTree(left, right), down: (node) => { node.children.forEach((c) => { c.count = node.count; c.value = Math.sign(c.count) * (c.right - c.left); }); }, up: (node) => { node.value = node.children.length ? node.children.reduce((a, v) => a + v.value, 0) : node.value;
if ( node.value === 0 ) { node.count = 0; node.children.length = 0; } }, }, ); } ans += BigInt(root.value) * BigInt(sorted[index + 1][0] - key); } return Number(ans % BigInt(10 ** 9 + 7));}export class SegTree { constructor( public left = 0, public right = 0, public value: number = 0, public count = 0, public children: SegTree[] = [], ) {}}
function insert( sweep: Map<number, [number, number, number][]>, left: number, down: number, up: number, diff: number,) { const arr = sweep.get(left) ?? []; arr.push([down, up, diff]); sweep.set(left, arr);}export function update< T extends { left: number; right: number; children: T[] },>( node: T, target: { left: number; right: number }, options: { modify: (a: T) => void; create: (target: { left: number; right: number }) => T; down: (a: T) => void; up: (a: T) => void; },): void { const { modify, create, down, up } = options; const current = node; if ( target.right < current.left || target.left > current.right ) { return; }
if ( target.left <= current.left && target.right >= current.right ) { if (node.children.length === 0) { modify(node);
return; } } else { if (node.children.length === 0) { const midx = [target.left, target.right].filter((a) => current.left < a && current.right > a )[0] ?? current.right;
const subinterval = OneSplit(current, midx);
if (subinterval.length) { node.children = subinterval.map( (c) => create(c), ); down(node); } } } if (node.children.length) { for (const child of node.children) { update(child, target, options); } up(node); }}export function OneSplit( current: { left: number; right: number }, midx: number,): { left: number; right: number }[] { const { left, right } = current;
if (left > right) return [];
if ((right - left) <= 1) return []; const mx = midx;
const lr = [ { left: left, right: mx }, { left: mx, right: right }, ];
const result = lr;
return result.filter( ({ left, right }) => left <= right && (right - left) && !(left === current.left && right === current.right), );}
Version Info