18407 - 가로 블록 쌓기

step 1

특별한 아이디어를 사용하는 것은 아닌 것 같습니다. 그냥 이 알고리즘을 알면 풀 수 있고 모르면 풀 수 없는 문제입니다. 우선 좌표가 너무 크니 좌표 압축을 해줍시다. 이러면 최대 좌표가 최악의 경우 200000이 됩니다.

 

만약 레이지 세그먼트 트리에 대해 알고 있으면 이 문제를 쉽게 해결할 수 있습니다.

step 2

세그먼트 트리에 "이 범위에 있는 블록 중 최대 높이"를 저장해 둡니다. 그리고 이번에 놓을 블록이 차지하는 범위 내에 있는 블록 중 최대 높이를 구합니다.

그 값에 1을 더한 다음 값을 덮어씌웁니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
#include<queue>
using namespace std;
int it[1000000],lit[1000000];
struct data {
	int x, y;
	inline bool operator<(const data& temp)const {
		return x < temp.x || x == temp.x && y < temp.y;
	}
}b[300000];
int t = 1;
int find(int s, int e, int i, int x, int y) {
	if (lit[i] != 0) {
		it[i] = max(it[i], lit[i]);
		if (i < t) {
			lit[i * 2] = max(lit[i * 2], lit[i]);
			lit[i * 2 + 1] = max(lit[i * 2 + 1], lit[i]);
		}
	}
	if (x <= s && e <= y) return it[i];
	if (e<x || s>y) return 0;
	return max(find(s, (s + e) / 2, i * 2, x, y), find((s + e) / 2 + 1, e, i * 2 + 1, x, y));
}
void update(int s, int e, int i, int x, int y, int v) {
	if (lit[i] != 0) {
		it[i] = max(it[i], lit[i]);
		if (i < t) {
			lit[i * 2] = max(lit[i * 2], lit[i]);
			lit[i * 2 + 1] = max(lit[i * 2 + 1], lit[i]);
		}
	}
	if (x <= s && e <= y) {
		it[i] = v;
		lit[i] = v;
		return;
	}
	if (e<x || s>y) return;
	update(s, (s + e) / 2, i * 2, x, y, v);
	update((s + e) / 2 + 1, e, i * 2 + 1, x, y, v);
	it[i] = max(it[i * 2], it[i * 2 + 1]);
}
int main() {
	int n, i;
	scanf("%d", &n);
	for (i = 1;i <= n;i++) {
		int x, y;
		scanf("%d%d", &x,&y);
		b[i * 2 - 1].x = y;
		b[i * 2].x = y + x - 1;
		b[i * 2 - 1].y = i * 2 - 1;
		b[i * 2].y = i * 2;
	}
	sort(b + 1, b + n + n + 1);
	int tv = -1, ttv = 0;
	for (i = 1;i <= n * 2;i++) {
		if (tv < b[i].x) ttv++;
		tv = b[i].x;
		b[i].x = ttv;
		swap(b[i].x, b[i].y);
	}
	sort(b + 1, b + n + n + 1);
	while (t < ttv) t <<= 1;
	for (i = 1;i <= n;i++) {
		int x = b[i * 2 - 1].y, y = b[i * 2].y;
		int v = find(1, t, 1, x, y);
		update(1, t, 1, x, y, v + 1);
	}
	printf("%d", it[1]);
	return 0;
}