Problem
https://www.acmicpc.net/problem/9251
Summary
부분 수열이 되는 수열 중 가장 긴 것을 찾는문제 ACAYKP와 CAPCAK의 LCS는 ACAK가 된다
Idea
LCS 문자열 출력은? https://www.acmicpc.net/problem/9252
Largest Rectangle
Problem
https://www.acmicpc.net/problem/6549
Summary
히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때
모든 막대 x에 대해서, x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾기
(1 ≤ n ≤ 100,000) h1, …, hn (0 ≤ hi ≤ 1000000000)
Idea
- 전 구간 중 가장 높이가 작은 것으로 만들 수 있는 총 넓이를 구한다
- 가장 작은 구간을 기준으로 좌/우 반복한다
static long largest(int s, int e) {
int x = e -s +1;
int idx = query(s, e);
long size = x * arr[idx];
if (s <= idx-1) {
long t = largest(s, idx-1);
if (size < t) {
size = t;
}
}
if (idx+1 <= e) {
long t = largest(idx+1, e);
if (size < t) {
size = t;
}
}
return size;
}
North-Western Winds
Problem
https://www.acmicpc.net/problem/5419
Summary
북서풍을 타고 항해할 수 있는 섬의 쌍의 수 구하기
섬의 수 n (1 ≤ n ≤ 75000) 섬의 좌표 xi, yi (-10^9 ≤ xi, yi ≤ 10^9)
Idea
- x 오름차순, y 내림차순 정렬
- y 구간을 tree로 표현해 좌표를 누적 구간합으로 표현, y값이 작은 섬들 개수를 세면 된다
- y 구간이 크므로 좌표를 압축할 필요가 있다
Related
Mars Maps
Problem
https://www.acmicpc.net/problem/3392
Summary
겹친 직사각형들의 총 넓이 구하기
지도의 수 N(1 ≤ N ≤ 10,000), (x1, y1)와 (x2, y2)은 직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표
x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)
Idea
native
N^3
for (x 만큼){
for (y 만큼) {
for (직사각형 개수 n만큼) {
if (x,y가 큰 직사각형에 포함되는지) {
sum update
}
}
}
}
flood fill
직사각형에 카운트 1을 채운다. 중복된 영역은 카운트 +1 을 해 최종적으로 카운트 1을 센다
plane sweeping with segment tree
- 각각의 직사각형의 시작 면(왼쪽면)과 끝면(오른쪽 면)을 list에 담아 x축으로 오름차순 정렬
시작면 x1,y1,y2,1
끝면 x2,y1,y2,-1
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
points[2*i] = new Point(x1, y1, y2, 0);
points[2*i+1] = new Point(x2, y1, y2, 1);
}
Arrays.sort(points);
-
x좌표를 sweep 하면서 넓이를 구해간다
-
x를 하나 꺼내 세로선 업데이트
세로선이 시작선일 경우, 해당 구간의 노드 값을 1 증가
새로선이 끝 선일 경우, 해당 구간의 노드 값을 1 감소 -
면적을 구한다 (높이= leaf 노드가 1 이상인 개수 query) (x - 이전 x) * 높이
업데이트 구간이 크므로 lazy update를 고려해야한다
대표값을 만나면 1로 마킹 후 업데이트 하지 않는다 (=node 구간크기)
void update(int node, int s, int e, int l, int r, int val) {
if (r < s || e < l) {
return;
}
if (l <= s && e <= r) {
tree[node][1] += val; // tree[node][1]: 중복 카운트, tree[node][0]: 1의 개수
} else {
int mid = (s + e) >> 1;
update(node * 2, s, mid, l, r, val);
update(node * 2 + 1, mid + 1, e, l, r, val);
}
if (tree[node][1] == 0) {
if (s == e)
tree[node][0] = 0;
else
tree[node][0] = tree[node * 2][0] + tree[node * 2 + 1][0];
} else {
tree[node][0] = e - s + 1;
}
}
Related
Light Switching
Problem
https://www.acmicpc.net/problem/1395
Summary
N개의 스위치, A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세기
스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)
Idea
node를 스위치의 on/off 상태로 정의한다면, node 카운트는 총 on의 스위치 개수이다
최대 10^6번 (10^6 * 17 = 천칠백만) 의 update가 일어날 수 있어 lazy update가 필요하다
static void update(int node, int s, int e, int l, int r) {
if (lazy[node] == 1) {
tree[node] = (e - s + 1) - tree[node];
if (s != e) {
lazy[node * 2] = (lazy[node * 2] == 0) ? 1 : 0;
lazy[node * 2 + 1] = (lazy[node * 2 + 1] == 0) ? 1 : 0;
}
lazy[node] = 0;
}
if (l > e || r < s) {
return;
}
if (l <= s && e <= r) {
tree[node] = (e - s + 1) - tree[node];
// 현재의 lazy는 위에서 처리되어 아래로 전달만 해준다
//lazy[node] = (lazy[node] == 0) ? 1 : 0;
if (s != e) {
lazy[node * 2] = (lazy[node * 2] == 0) ? 1 : 0;
lazy[node * 2 + 1] = (lazy[node * 2 + 1] == 0) ? 1 : 0;
}
return;
}
if ( s != e) {
int mid = (s + e) / 2;
update(node * 2, s, mid, l, r);
update(node * 2 + 1, mid + 1, e, l, r);
tree[node] = tree[node*2] + tree[node*2 + 1];
}
}