http://codeforces.com/blog/entry/22616
<Segment Tree + DP>
Codeforces #426 (Div. 1) B - The Bakery http://codeforces.com/contest/833/problem/B
<Segment Tree + Binary Search>
1321 군인 https://www.acmicpc.net/problem/1321
9426 중앙값 측정 https://www.acmicpc.net/problem/9426
1849 순열 https://www.acmicpc.net/problem/1849
<Segment Tree + Plane sweeping>
2185 직사각형의 합집합 https://www.acmicpc.net/problem/2185
3392 화성지도 https://www.acmicpc.net/problem/3392
7626 직사각형 https://www.acmicpc.net/problem/7626
<Segment Tree + Divide & conquer>
14727 퍼즐 자르기 https://www.acmicpc.net/problem/14727
1. <Segment Tree + DP>
- Codeforces #426 (Div. 1) B - The Bakery
$N$개의 케이크의 종류가 주어지고 $K$개의 박스가 있다.
케이크를 순서대로 묶어서 $K$개의 박스에 넣을 때 박스에 들어있는 케이크의 종류의 합을
최대화 시키는 문제이다.
(박스에 들어있는 케이크의 종류의 갯수 : $T_{i}$이면 $max$ $\sum_{i=1}^{K} T_{i}$를 구해야한다.
풀이가 직관적으로 이해하기 어렵다.
DP는 DP인데 segment tree로만을 이용한 DP? 같은 느낌이다.
$K$가 1인 경우는 set을 이용하면 구할 수 있다.
$K$가 1보다 큰 경우에 segment tree를 이용한다.
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxN = 35100;
int n, k;
int dp[55][maxN];
int a[maxN], pre[maxN], last[maxN];
int segt[1 << 17], lazy[1 << 17];
void build(int ki, int node, int l, int r) {
lazy[node] = 0;
if (l == r) {
segt[node] = dp[ki][l];
return;
}
int mid = (l + r) >> 1, nxt = node << 1;
build(ki, nxt, l, mid);
build(ki, nxt + 1, mid + 1, r);
segt[node] = max(segt[nxt], segt[nxt + 1]);
}
void lazyprop(int node, int l, int r) {
if (!lazy[node])
return;
segt[node] += lazy[node];
if (l != r) {
int nxt = node << 1;
lazy[nxt] += lazy[node];
lazy[nxt + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int i, int j) {
lazyprop(node, l, r);
if (l>r || i>r || j<l)
return;
if (i <= l && j >= r) {
lazy[node] = 1;
lazyprop(node, l, r);
return;
}
int mid = (l + r) >> 1, nxt = node << 1;
update(nxt, l, mid, i, j);
update(nxt + 1, mid + 1, r, i, j);
segt[node] = max(segt[nxt], segt[nxt + 1]);
}
int query(int node, int l, int r, int i, int j) {
lazyprop(node, l, r);
if (l>r || i>r || j<l)
return 0;
if (i <= l && j >= r)
return segt[node];
int mid = (l + r) >> 1, nxt = node << 1;
return max(query(nxt, l, mid, i, j), query(nxt + 1, mid + 1, r, i, j));
}
int main(int argc, char ** argv) {
cin >> n >> k;
for (int i = 0; i<n; i++) {
cin >> a[i];
if (last[a[i]])
pre[i] = last[a[i]]; //이전의 index를 넣어줌
last[a[i]] = i;
}
set<int> k0;
for (int i = 0; i<n; i++) {
k0.insert(a[i]);
dp[0][i] = k0.size();
}
for (int i = 1; i<k; i++) {
build(i - 1, 1, 0, n - 1); //dp[i-1][j]를 세그먼트 트리 노드에 삽입
for (int j = i; j<n; j++) {
update(1, 0, n - 1, pre[j], j - 1); //a[j]와 같은 값이 나오는 이전값 ~
dp[i][j] = max(dp[i - 1][j], query(1, 0, n - 1, 0, j));
}
}
cout << dp[k - 1][n - 1] << '\n';
return 0;
}
| cs |
2. <Segment Tree + Binary Search>
- 군인
부대의 수가 줄어들거나 늘어날 수가 있다.
군인은 부대의 정원에 맞게 차례대로 들어간다.
해당 군인이 어디 부대에 있는지 쿼리를 처리하는 문제다.
세그먼트 트리로 처리할 수 있다.
update부분은 동일한데 query부분이 특이하다.
이분탐색을 세그먼트트리에 적용한것이다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Segment {
int size;
vector<int> tree;
void init(int N) { tree.resize(4 * N, 0); size = N; }
int update(int idx, int val, int node, int nl, int nr) {
if (idx < nl || idx > nr) return tree[node];
if (nl == nr) return tree[node] += val;
int mid = (nl + nr) >> 1;
return tree[node] = update(idx, val, node * 2, nl, mid) +
update(idx, val, node * 2 + 1, mid + 1, nr);
}
int update(int idx, int val) {
return update(idx, val, 1, 0, size - 1);
}
int query(int val, int node, int nl, int nr) {
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
if (tree[node * 2] >= val) return query(val, node * 2, nl, mid);
else return query(val - tree[node * 2], node * 2 + 1, mid + 1, nr);
}
int query(int val) {
return query(val, 1, 0, size - 1);
}
};
int N, M;
Segment seg;
int main() {
scanf("%d", &N);
seg.init(N);
for (int n = 0, v;n < N;n++) {
scanf("%d", &v);
seg.update(n, v);
}
scanf("%d", &M);
for (int m = 0;m < M;m++) {
int a, b, c;
scanf("%d", &a);
if (a == 1) {
scanf("%d%d", &b, &c);
b--;
seg.update(b, c);
}
else {
scanf("%d", &b);
printf("%d\n", seg.query(b) + 1);
}
}
return 0;
}
| cs |
- 순열
근본적인 풀이부터 좀 헤맸던 문제.
1부터 N까지 수열이 있는데 $i$보다 큰 수들의 개수가 저장되있는 A[$i$]가 주어진다.
역으로 원본 수열을 구하는 문제이다.
만약 원본수열의 아직 넣지 않은 인덱스들을 모아놓는 자료구조가 있다면
$i$는 ans[A[$i$] + 1]번째 인덱스로 들어간다. (그림 그려보면 나옴)
이 자료구조를 set, vector, map으로 구현해 보려고 했는데 실패해서
segment tree + binary search를 이용하기로 했다.
풀고나서 이렇게 푼 사람 별로없을것 같아 뿌듯했는데 정해가 이 방법이다...
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct Segment {
int Size;
vector<int> tree;
Segment(int s) :Size(s) { tree.resize(4 * s, 0); }
int update(int val, int idx, int node, int nl, int nr) {
if (idx < nl || idx > nr) return tree[node];
if (nl == nr) return tree[node] += val;
int mid = (nl + nr) >> 1;
return tree[node] = update(val, idx, node * 2, nl, mid) +
update(val, idx, node * 2 + 1, mid + 1, nr);
}
void update(int val, int idx) {
update(val, idx, 1, 0, Size - 1);
}
int query(int val, int node, int nl, int nr) {
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
if (tree[node * 2] >= val) return query(val, node * 2, nl, mid);
else return query(val - tree[node * 2], node * 2 + 1, mid + 1, nr);
}
int query(int val) {
return query(val, 1, 0, Size - 1);
}
};
int N;
int A[100001];
int ans[100001];
int main() {
scanf("%d", &N);
for (int n = 1;n <= N;n++) scanf("%d", &A[n]);
Segment seg(N);
for (int n = 1;n <= N;n++)
seg.update(1, n - 1);
for (int n = 1;n <= N;n++) {
int idx = seg.query(A[n] + 1);
ans[idx + 1] = n;
seg.update(-1, idx);
}
for (int n = 1;n <= N;n++) printf("%d\n", ans[n]);
return 0;
}
| cs |
- 중앙값 측정
multiset 2개로 풀 수 있긴하나 솔직히 복잡하다.
이 문제도 segment tree + binary search로 해결할 수 있다.
3. <Segment Tree + Plane Sweeping>
구간 [i, j]에서 0보다 큰값을 가지고있는 노드들의 갯수를 세는 방식도 잘 기억하자!
- 직사각형의 합집합
겹칠 수 있는 직사각형들이 주어지고 이 직사각형의 합집합의 둘레를 구하는 문제다.
y축과 평행한 선을 기준으로 삼고 맨 왼쪽부터 오른쪽으로 가면서 훑는 plane sweeping 작업을 한다.
각 직사각형의 y가 작은 x선, x가 큰 y선에 각각 +1, -1을 넣으며 segment tree에 update하는 형식이다.
y축 기준으로, x축 기준으로 결과를 저장하면 된다.
<주의사항>
- 정렬을 X가 작은순서 그다음으로 +1인 순서로 해야한다.
다음과 같이 빨강직사각형의 끝선(1)과 파랑직사각형의 시작선(2)의 x축이 동일하다고 가정해보자.
- (2)가 먼저 update되고 (1)이 나중에 됨
우리가 구하고자 하는 왼쪽에서 봤을때의 둘레의 합이 구해질 것이다. <result = (1) + (2) - (1)>
- (1)이 먼저 update되고 (2)가 나중에 됨
(1)이 두번 더해질 것이다. <result = (1) + (2)>
- segment tree를 update시킬 때 구간의 마지막값 -1을 해서 넣어줘야한다.
이건 update구현에 따라 다를 수 있는데 정렬시키기 전에 -1을 하는 실수를 하지 말자.
3. <Segment Tree + Plane Sweeping>
구간 [i, j]에서 0보다 큰값을 가지고있는 노드들의 갯수를 세는 방식도 잘 기억하자!
- 직사각형의 합집합
겹칠 수 있는 직사각형들이 주어지고 이 직사각형의 합집합의 둘레를 구하는 문제다.
y축과 평행한 선을 기준으로 삼고 맨 왼쪽부터 오른쪽으로 가면서 훑는 plane sweeping 작업을 한다.
각 직사각형의 y가 작은 x선, x가 큰 y선에 각각 +1, -1을 넣으며 segment tree에 update하는 형식이다.
y축 기준으로, x축 기준으로 결과를 저장하면 된다.
<주의사항>
- 정렬을 X가 작은순서 그다음으로 +1인 순서로 해야한다.
- (2)가 먼저 update되고 (1)이 나중에 됨
우리가 구하고자 하는 왼쪽에서 봤을때의 둘레의 합이 구해질 것이다. <result = (1) + (2) - (1)>
- (1)이 먼저 update되고 (2)가 나중에 됨
(1)이 두번 더해질 것이다. <result = (1) + (2)>
- segment tree를 update시킬 때 구간의 마지막값 -1을 해서 넣어줘야한다.
이건 update구현에 따라 다를 수 있는데 정렬시키기 전에 -1을 하는 실수를 하지 말자.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 20001
typedef pair<pair<int, pair<int, int>>, int> P;
struct Segment {
vector<int> tree, cnt;
Segment(){ tree.resize(4 * MAX, 0), cnt.resize(4 * MAX, 0); }
void update(int val, int l, int r, int node, int nl, int nr) {
if (r < nl || l > nr) return;
if (l <= nl && nr <= r) tree[node] += val;
else {
int mid = (nl + nr) >> 1;
update(val, l, r, node * 2, nl, mid);
update(val, l, r, node * 2 + 1, mid + 1, nr);
}
if (tree[node]) cnt[node] = nr - nl + 1;
else {
if (nl == nr) cnt[node] = 0;
else cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
}
}
void update(int val, int l, int r) {
update(val, l, r, 1, 0, MAX - 1);
}
int query() {
return cnt[1];
}
};
int N, ans;
int rect[5000][4];
vector<P> adj;
void get() {
Segment seg;
sort(adj.begin(), adj.end(), [](P a, P b)->bool {
if(a.first.first == b.first.first)
return a.second > b.second;
return a.first.first < b.first.first;
});
for (auto n : adj) {
int fir = seg.query();
seg.update(n.second, n.first.second.first, n.first.second.second - 1);
int sec = seg.query();
ans += abs(fir - sec);
}
adj.clear();
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) {
for (int m = 0;m < 4;m++)
scanf("%d", &rect[n][m]), rect[n][m] += 10000;
if (rect[n][0] > rect[n][2]) swap(rect[n][0], rect[n][2]);
if (rect[n][1] > rect[n][3]) swap(rect[n][1], rect[n][3]);
}
for (int n = 0;n < N;n++) {
adj.push_back({ { rect[n][0], { rect[n][1],rect[n][3]} }, 1 });
adj.push_back({ { rect[n][2], { rect[n][1],rect[n][3]} }, -1 });
}
get();
for (int n = 0;n < N;n++) {
adj.push_back({ { rect[n][1], {rect[n][0],rect[n][2]}}, 1 });
adj.push_back({ { rect[n][3], {rect[n][0],rect[n][2]}}, -1});
}
get();
printf("%d\n", ans);
return 0;
}
| cs |
- 화성지도
위에선 둘레를 구했다면 이번엔 면적을 구하는 문제이다. 좀더 쉬운듯하다.
비슷한 방식인데 이전 x값과 현재 x값의 차이를 전체 구간에서 1이상인 점들의 갯수와 곱해주면 된다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 30001
typedef pair<pair<int, int>, pair<int, int>> P;
struct Segment {
vector<int> tree, cnt;
Segment() { tree.resize(4 * MAX, 0), cnt.resize(4 * MAX, 0); }
void update(int val, int l, int r, int node, int nl, int nr) {
if (r < nl || l > nr) return;
if (l <= nl && nr <= r) tree[node] += val;
else {
int mid = (nl + nr) >> 1;
update(val, l, r, node * 2, nl, mid);
update(val, l, r, node * 2 + 1, mid + 1, nr);
}
if (tree[node]) cnt[node] = nr - nl + 1;
else {
if (nl == nr) cnt[node] = 0;
else cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
}
}
void update(int val, int l, int r) {
update(val, l, r, 1, 0, MAX - 1);
}
int query() {
return cnt[1];
}
};
int N;
vector<P> rect;
int main() {
Segment seg;
scanf("%d", &N);
for (int n = 0;n < N;n++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
rect.push_back({ { x1,1 },{ y1,y2 - 1 } });
rect.push_back({ { x2,-1 }, { y1,y2 - 1 } });
}
sort(rect.begin(), rect.end());
int ans = 0, prev = -1;
for (auto n : rect) {
int curr = n.first.first;
if (prev != -1) {
int diff = curr - prev;
ans += diff*seg.query();
}
seg.update(n.first.second, n.second.first, n.second.second);
prev = curr;
}
printf("%d\n", ans);
return 0;
}
| cs |
- 직사각형
화성지도와 동일한 문제이나 좌표가 $10^{9}$까지 들어오기때문에 좌표압축이 필요하다.
알고리즘은 동일하다.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<int> ypos;
struct Segment {
int size;
vector<int> tree, cnt;
Segment() {}
Segment(int s) :size(s) { tree.resize(4 * size, 0); cnt.resize(4 * size, 0); }
void update(int val, int l, int r, int node, int nl, int nr) {
if (nr < l || nl > r) return;
if (l <= nl && nr <= r) tree[node] += val;
else {
int mid = (nl + nr) >> 1;
update(val, l, r, node * 2, nl, mid);
update(val, l, r, node * 2 + 1, mid + 1, nr);
}
if (tree[node]) cnt[node] = ypos[nr + 1] - ypos[nl];
else {
if (nl == nr) cnt[node] = 0;
else cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
}
}
void update(int val, int l, int r) {
update(val, l, r, 1, 0, size - 1);
}
int query() { return cnt[1]; }
};
struct Line {
int x, y1, y2;
int c;
Line() {}
Line(int xx, int yy1, int yy2, int cc) :x(xx), y1(yy1), y2(yy2), c(cc) {}
};
int N;
vector<int> save_y;
vector<Line> line;
map<int, int> mat;
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) {
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
line.emplace_back(Line(x1, y1, y2, 1));
line.emplace_back(Line(x2, y1, y2, -1));
save_y.emplace_back(y1);
save_y.emplace_back(y2);
}
sort(line.begin(), line.end(), [](Line &a, Line &b)->bool {
return a.x < b.x;
});
sort(save_y.begin(), save_y.end());
save_y.erase(unique(save_y.begin(), save_y.end()), save_y.end());
for (int n = 0;n < save_y.size();++n) {
mat[save_y[n]] = n;
ypos.emplace_back(save_y[n]);
}
Segment seg(save_y.size());
long long ans = 0;
for (int n = 0;n < line.size();++n) {
if (n) ans += 1LL * (line[n].x - line[n - 1].x)*seg.query();
int y1 = line[n].y1, y2 = line[n].y2;
seg.update(line[n].c, mat[line[n].y1], mat[line[n].y2] - 1);
}
printf("%lld\n", ans);
return 0;
}
| cs |
4. <Segment Tree + Divide & conquer>
- 퍼즐 자르기
상당히 유명한 문제다.
히스토그램, 히스토그램에서 가장 큰 직사각형 등의 동일 문제가 있다.
분할정복과 segment tree를 접목시켜 풀때는 segment tree에 최소높이의 index를 넣어준다.
구간 [left, right]에서 [left, index - 1], [index + 1, right]으로 분할정복해 나가는것이다.
- 퍼즐 자르기
상당히 유명한 문제다.
히스토그램, 히스토그램에서 가장 큰 직사각형 등의 동일 문제가 있다.
분할정복과 segment tree를 접목시켜 풀때는 segment tree에 최소높이의 index를 넣어준다.
구간 [left, right]에서 [left, index - 1], [index + 1, right]으로 분할정복해 나가는것이다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
ll height[100001];
struct Segment {
vector<int> tree;
Segment(int S) { tree.resize(4 * S, 0); }
void init(int node, int nl, int nr) {
if (nl == nr) {
tree[node] = nl;
}
else {
int mid = (nl + nr) >> 1;
init(node * 2, nl, mid);
init(node * 2 + 1, mid + 1, nr);
if (height[tree[node * 2]] < height[tree[node * 2 + 1]])
tree[node] = tree[node * 2];
else
tree[node] = tree[node * 2 + 1];
}
}
void init() {
init(1, 0, N - 1);
}
int query(int l, int r, int node, int nl, int nr) {
if (nr < l || r < nl) return -1;
if (l <= nl && nr <= r) return tree[node];
int mid = (nl + nr) >> 1;
int a = query(l, r, node * 2, nl, mid);
int b = query(l, r, node * 2 + 1, mid + 1, nr);
if (a == -1) return b;
if (b == -1) return a;
if (height[a] < height[b]) return a;
else return b;
}
long long solve(int l, int r) {
int idx = query(l, r, 1, 0, N - 1);
long long ret = (long long)(r - l + 1) * height[idx];
if (l <= idx - 1) ret = max(ret, solve(l, idx - 1));
if (idx + 1 <= r) ret = max(ret, solve(idx + 1, r));
return ret;
}
};
int main() {
scanf("%d", &N);
Segment seg(N);
for (int n = 0;n < N;n++) scanf("%lld", &height[n]);
seg.init();
printf("%lld\n", seg.solve(0, N - 1));
return 0;
}
| cs |
댓글 없음:
댓글 쓰기