1280 나무 심기 https://www.acmicpc.net/problem/1280
7578 공장 https://www.acmicpc.net/problem/7578
9463 순열 그래프 https://www.acmicpc.net/problem/9463
3770 대한민국 https://www.acmicpc.net/problem/3770
2517 달리기 https://www.acmicpc.net/problem/2517
9345 디지털 비디오 디스크(DVDs) https://www.acmicpc.net/problem/9345
1. 영화 수집
처음엔 DVD가 위에서부터 오름차순 번호로 쌓여있다.
상근이가 $i$번 영화를 볼때는 $i$번째 DVD를 빼서 맨 위에 쌓는다.
이러한 작업을 했을 때마다 $i$번째 DVD를 빼기 전 위에 DVD개수를 구하는 문제이다.
이 문제를 보고 바로 Segment tree를 떠올리기는 쉽지 않다.
또한 적용시키기도 꽤나 어려워 보인다.
여기서 포인트는 M개의 쿼리를 처리해야 하기 때문에 기존의 N개와 추가 노드 M개를 만드는 것이다.
위 그림과 같이 tree를 초기화 시켜준다.
왼쪽의 배열은 현재 DVD가 위치한 node의 index를 저장하고있다.
(아래 코드에서의 'i' 변수가 수행)
$i$번째 DVD를 빼기 전 위에있는 DVD의 개수는 0번 node부터 $i$번째 node의 index-1 까지의
구간 합이라고 볼 수 있다.
#include <cstdio>
#include <vector>
using namespace std;
struct Segment {
int size;
vector<int> tree, idx;
Segment(int N, int M) {
size = N + M;
idx.resize(N);
tree.resize(4 * size, 0);
}
int init(int node, int M, int l, int r) {
if (l == r) {
if (l >= M) {
idx[l - M] = l;
tree[node] = 1;
}
return tree[node];
}
int mid = (l + r) / 2;
return tree[node] = init(node * 2, M, l, mid) + init(node * 2 + 1, M, mid + 1, r);
}
void init(int M) {
init(1, M, 0, size - 1);
}
int query(int node, int l, int r, int nL, int nR) {
if (r < nL || l > nR) return 0;
if (l <= nL && nR <= r) {
return tree[node];
}
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) + query(node * 2 + 1, l, r, mid + 1, nR);
}
int query(int left, int right) {
return query(1, left, idx[right] - 1, 0, size - 1);
}
int update(int idx, int node, int val, int nL, int nR) {
if (idx < nL || nR < idx) return tree[node];
if (nL == nR) return tree[node] = val;
int mid = (nL + nR) / 2;
return tree[node] = update(idx, node * 2, val, nL, mid) + update(idx, node * 2 + 1, val, mid + 1, nR);
}
int update(int index, int val) {
return update(idx[index], 1, val, 0, size - 1);
}
void change(int index, int val) {
idx[index] = val;
}
};
int N, M;
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
Segment seg(N, M);
seg.init(M);
int i = M - 1;
while (M--) {
int u;
scanf("%d", &u);
u--;
printf("%d ", seg.query(0, u));
seg.update(u, 0);
seg.change(u, i--);
seg.update(u, 1);
}
printf("\n");
}
return 0;
}
| cs |
2. 나무 심기
나무를 심는데 비용이 발생한다.
이 비용은 전까지 심었던 나무와 지금 나무의 거리의 합이다.
모든 나무를 심는데 드는 비용의 곱을 구하는 문제이다.
입력이 정렬되있지 않고 중복된 값도 들어오기 때문에 기존의 구간합으로는 구하기 힘들다.
node를 나무들의 좌표를 기준으로 Segment tree를 구성하면 해결할 수 있다.
현재 나무보다 큰나무들의 합, 작은 나무들의 합, 큰 나무들의 개수, 작은 나무들의 개수를 구해서
해결하면 된다.
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 200001
#define mod 1000000007
typedef long long ll;
struct Segment {
vector<ll> tree;
int size;
Segment() {
tree.resize(4 * MAX, 0);
size = MAX;
}
ll update(int idx, int node, ll val, int nL, int nR) {
if (idx < nL || idx > nR) return tree[node];
if (nL == nR) {
return tree[node] += val;
}
int mid = (nL + nR) / 2;
return tree[node] = update(idx, node * 2, val, nL, mid) + update(idx, node * 2 + 1, val, mid + 1, nR);
}
ll update(int idx, ll val) {
return update(idx, 1, val, 0, size - 1);
}
ll query(int node, int l, int r, int nL, int nR) {
if (r < nL || l > nR) return 0;
if (l <= nL && nR <= r) return tree[node];
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) + query(node * 2 + 1, l, r, mid + 1, nR);
}
ll query(int l, int r) {
return query(1, l, r, 0, size - 1);
}
};
int N;
int input;
int main() {
Segment seg_sum, seg_cnt;
scanf("%d", &N);
scanf("%d", &input);
seg_sum.update(input, input); // 구간 거리 합
seg_cnt.update(input, 1); // 구간 카운트 합
long long ans = 1;
for (int n = 1;n < N;n++) {
scanf("%d", &input);
seg_sum.update(input, input);
seg_cnt.update(input, 1);
ll sum1 = seg_sum.query(0, input - 1); //기준보다 작은경우
ll sum2 = seg_sum.query(input + 1, MAX); //기준보다 큰 경우
ll cnt1 = seg_cnt.query(0, input - 1);
ll cnt2 = seg_cnt.query(input + 1, MAX);
ll cost = (sum2 - input*cnt2) % mod + (input*cnt1 - sum1) % mod;
ans *= cost%mod;
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
| cs |
3. 공장, 순열 그래프, 대한민국
푸는 방법은 금방 깨달아도 구현하는데 어떻게 할지 몰라서 막막했던 문제이다.
일단 푸는 방법은 밑의 그림처럼 숫자를 index로 변환 시킨 후 자기 자신보다 작은 index가 앞에있다면
교차하는것이기 때문에 갯수를 세면 된다.
첫 숫자 392는 2번 index이므로 앞에 있는 index중 작은 index는 노란색 선인 1번 index가 있기때문에 1개 교차한다.
351도 마찬가지 방법으로 하면 2개 교차한다.
문제는 이 방법을 어떻게 적용하는가 이다.
적용할 방법을 찾지 못하다가 결국 힌트(Inversion)를 보고 풀게되었다.
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
struct Segment {
int size;
vector <ll> tree;
Segment(int s) {
size = s;
tree.resize(4 * s, 0);
}
ll 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) / 2;
return tree[node] = update(idx, val, node * 2, nL, mid) + update(idx, val, node * 2 + 1, mid + 1, nR);
}
ll update(int idx, int val) {
return update(idx, val, 1, 0, size - 1);
}
ll query(int node, int l, int r, int nL, int nR) {
if (r < nL || l >nR) return 0;
if (l <= nL && nR <= r) return tree[node];
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) + query(node * 2 + 1, l, r, mid + 1, nR);
}
ll query(int l, int r) {
return query(1, l, r, 0, size - 1);
}
};
int N;
int arr[500001];
int map[1100000];
int main() {
scanf("%d", &N);
Segment seg(N);
for (int n = 1, u;n <= N;n++) {
scanf("%d", &u);
map[u] = n;
}
for (int n = 0, u;n < N;n++) {
scanf("%d", &u);
arr[n] = map[u];
}
ll ans = 0;
for (int n = 0;n < N;n++) {
ans += (n - seg.query(0, arr[n]));
seg.update(arr[n], 1);
}
printf("%lld\n", ans);
return 0;
}
| cs |
4. 달리기
현재 등수에 있는 선수들의 달리기 실력이 주어진다.
달리기 실력은 서로 다를때 각 선수의 최선의 등수를 구하는 문제이다.
전형적인 segment tree문제이다.
쿼리마다 자기 앞에있는 선수 중 실력이 작은 선수는 재낄 수 있기 때문에 이 값을 구해준다.
현재 인덱스에서 이 값을 뺀값이 최선의 등수가 된다.
실력이 $10^9$까지 들어와 배열에 저장할 수 없으므로 map에 저장시켰다.
#include <vector>
#include <algorithm>
#include <unordered_map>
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 l, int r, int node, int nl, int nr) {
if (nr < l || nl > r) return 0;
if (l <= nl && nr <= r) return tree[node];
int mid = (nl + nr) >> 1;
return query(l, r, node * 2, nl, mid) + query(l, r, node * 2 + 1, mid + 1, nr);
}
int query(int l, int r) {
return query(l, r, 1, 0, Size - 1);
}
};
int N;
int arr[500001];
unordered_map<int, int> save;
int main() {
vector<int> v;
scanf("%d", &N);
for (int n = 1;n <= N;n++) scanf("%d", &arr[n]), v.emplace_back(arr[n]);
sort(v.begin(), v.end());
for (int s = 0;s < v.size();++s) {
save[v[s]] = s;
}
Segment seg(N);
for (int n = 1;n <= N;n++) {
int get = save[arr[n]];
printf("%d\n", n - seg.query(0, get));
seg.update(1, get);
}
return 0;
}
| cs |
5. 디지털 비디오 디스크(DVDs)
DVD들이 N개 존재하는데 두가지 query를 시행한다.
1. A번째 DVD와 B번째 DVD를 swap한다.
2. A부터 B번째 DVD까지 DVD가 존재하는지 확인한다.
(순서는 상관없다.)
min, max segment tree를 구현해서 풀 수 있다.
구간에 최소, 최대가 각각 A, B이면 범위안의 DVD들이 존재하는것이다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
struct Segment {
vector<int> Max, Min;
int size;
Segment(int s) :size(s) { Max.resize(4 * s, 0), Min.resize(4 * s, INF); }
void init(int node, int nl, int nr) {
if (nl == nr) {
Min[node] = Max[node] = nl;
return;
}
int mid = (nl + nr) >> 1;
init(node * 2, nl, mid), init(node * 2 + 1, mid + 1, nr);
Min[node] = min(Min[node * 2], Min[node * 2 + 1]);
Max[node] = max(Max[node * 2], Max[node * 2 + 1]);
}
void init() {
init(1, 0, size - 1);
}
void update(int val, int idx, int node, int nl, int nr) {
if (nr < idx || idx < nl) return;
if (nl == nr) {
Min[node] = Max[node] = val;
return;
}
int mid = (nl + nr) >> 1;
update(val, idx, node * 2, nl, mid), update(val, idx, node * 2 + 1, mid + 1, nr);
Min[node] = min(Min[node * 2], Min[node * 2 + 1]);
Max[node] = max(Max[node * 2], Max[node * 2 + 1]);
}
void update(int val, int idx) {
update(val, idx, 1, 0, size - 1);
}
//return {Min, Max}
pair<int, int> query(int l, int r, int node, int nl, int nr) {
if (l > nr || nl > r) return { INF,0 };
if (l <= nl && nr <= r) { return { Min[node],Max[node] }; }
int mid = (nl + nr) >> 1;
auto f = query(l, r, node * 2, nl, mid);
auto s = query(l, r, node * 2 + 1, mid + 1, nr);
return { min(f.first,s.first), max(f.second,s.second) };
}
pair<int, int> query(int l, int r) {
return query(l, r, 1, 0, size - 1);
}
};
int N, M;
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
Segment seg(N);
seg.init();
for (int m = 0;m < M;m++) {
int q, u, v;
scanf("%d%d%d", &q, &u, &v);
if (!q) {
auto A = seg.query(u, u);
auto B = seg.query(v, v);
seg.update(B.first, u);
seg.update(A.first, v);
}
else {
auto get = seg.query(u, v);
if (get.first == u && get.second == v) printf("YES\n");
else printf("NO\n");
}
}
}
return 0;
}
| cs |
영화 수집 문제 덕분에 이해했습니다. 감사합니다.
답글삭제