백준10070 벽

작성일 | In

문제 링크

  • http://icpc.me/10070

문제 출처

  • 2014 IOI Day1 2번

사용 알고리즘

  • Segment Tree
  • Lazy Propagation

시간 복잡도

  • O(N log N)

풀이

각 벽을 세그먼트 트리의 리프 노드에 할당해줍시다.
세그먼트 트리의 각 노드들은 구간의 lower/upper bound를 저장하고 있습니다.

add연산은 lower bound를 변화시키고, remove연산은 upper bound연산을 변화시킵니다.
Lazy Propagation을 이용해 업데이트를 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "wall.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p; //lower bound, upper bound

int *ans;
p tree[1 << 22];

void push(int node, int op, ll v){
	if(op == 1){
		tree[node].x = max(tree[node].x, v);
		tree[node].y = max(tree[node].y, v);
	}else{
		tree[node].x = min(tree[node].x, v);
		tree[node].y = min(tree[node].y, v);
	}
}

void update(int node, int s, int e, int l, int r, int op, ll v){
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		push(node, op, v);
		ans[l] = tree[node].x;
		return;
	}
	int m = s + e >> 1;
	push(node*2, 1, tree[node].x);
	push(node*2, 2, tree[node].y);
	push(node*2+1, 1, tree[node].x);
	push(node*2+1, 2, tree[node].y);
	tree[node].x = 0, tree[node].y = 1e9;
	update(node*2, s, m, l, r, op, v);
	update(node*2+1, m+1, e, l, r, op, v);
}

void buildWall(int n, int k, int op[], int lf[], int rf[], int h[], int res[]){
	ans = res;
	for(int i=0; i<k; i++){
		update(1, 0, n-1, lf[i], rf[i], op[i], h[i]);
	}
	for(int i=0; i<n; i++){
		update(1, 0, n-1, i, i, 1, 0);
	}
}