TS) 백준 7578번: 공장

https://www.acmicpc.net/problem/7578

7578번: 공장

 

10090번이랑 똑같은 문제

 

 

// https://www.acmicpc.net/problem/7578
// 공장
class Item {
	constructor(public value = 0) {}
}

class SegmentTree {
	private lg: number;
	private sz: number;
	private tree: Array<Item>;

	constructor(inputArray: Array<number>) {
		const inputArrayLength = inputArray.length;

		this.lg = Math.ceil(Math.log2(inputArrayLength));

		this.sz = 1 << this.lg;

		this.tree = Array.from(new Array(this.sz << 1), () => new Item());

		for (let i = 1; i <= inputArrayLength; i++) {
			this.tree[(i - 1) | this.sz] = new Item(inputArray[i - 1]);
		}

		for (let i = this.sz - 1; i > 0; i--) {
			this.tree[i] = this.merge(this.tree[i << 1], this.tree[(i << 1) | 1]);
			//  i << 1 은 왼쪽 자식 노드    i * 2
			// (i << 1) | 1 은 오른쪽 자식 노드 i * 2 + 1
		}
	}

	private merge(A: Item, B: Item): Item {
		return new Item(A.value + B.value);
	}

	private update(value: number, item: Item): Item {
		return new Item(item.value + value);
	}

	private apply(i: number, value: number) {
		this.tree[i] = this.update(value, this.tree[i]);
	}

	private pull(i: number) {
		this.tree[i] = this.merge(this.tree[i << 1], this.tree[(i << 1) | 1]);
	}

	public updatePoint(i: number, value: number) {
		i = (i - 1) | this.sz;
		this.apply(i, value);
		for (let j = 1; j <= this.lg; j++) this.pull(i >> j);
	}

	queryPoint(i: number) {
		i = (i - 1) | this.sz;
		return this.tree[i].value;
	}

	queryRange(l: number, r: number) {
		let L = new Item();
		let R = new Item();

		l = (l - 1) | this.sz;
		r = (r - 1) | this.sz;

		for (; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) L = this.merge(L, this.tree[l++]);
			if (~r & 1) R = this.merge(this.tree[r--], R);
		}
		return this.merge(L, R).value;
	}
}
const input: string[] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input[0]!;
const nums = input[1].split(' ');
const hashMap = input[2].split(' ').reduce((r: Map<string, number>, v: string, i: number) => {
	r.set(v, i + 1);
	return r;
}, new Map());

const segmentTree = new SegmentTree(Array(N + 1).fill(0));

let answer = 0;
nums.forEach((num) => {
	const hash = hashMap.get(num)!;
	segmentTree.updatePoint(hash, 1);
	answer += segmentTree.queryRange(hash + 1, N);
});
console.log(answer);