semteo선생님께서 숙제로 내주신 Dynamic Segment Tree와 Persistent Segment Tree를 공부했다.
PST로 문제들을 풀면서 엄청난 WA, Segfault를 맛보았다. 개념은 생각보다 어렵지 않고, 구현이 좀 까다로운 것 같다. 나는 jhnah917님 글을 보고 공부했다.
그리고 내가 좋아하는 트리 문제가 마려워서 오픈톡에 가서 추천을 받았다. Ibory라는 고수분이 추천해주신 트리 문제 2개를 풀어보았다. 재밌었다!
청정수컵도 끝나서 시간이 좀 여유 있다. 그래서 간만에 열심히 문제를 푼 것 같다! 근데 PST 구현 때문에 쓴 시간에 비해 푼 문제수는 적긴 한 듯.. ㅠ 구현 실력이 쌉구리다.
요즘 드는 생각인데 나는 구현에 정말 약한 것 같다. 코포할 때 특히 많이 느끼는데, C, D에 구현이 조금 더러운 셋이 나오면 항상 망한다. 코포할 때는 의외로 그리디, 이분탐색, 애드 혹에 꽤 강한 모습을 보이고 있다. 그치만, 뭔가 조금이라도 지저분한 구현을 요구하는 문제는 진짜 잘 못 푸는 것 같다. 그리고 DP도 잘 못하는 듯..
암튼 시작해보자.
풀이는 그냥 혼자 복기용으로 쓰는 거라 첨 푸시는 분들이 이해하긴 어려울 수 있습니다..
PST 첫 문제로 이 문제를 풀었다. 사실 PST없이도 풀리는 문제지만, 문제 내용 자체가 PST의 개념을 담고 있어서 좋은 것 같다. 쿼리가 2개 주어진다. 1번 쿼리는 기존에 세그 문제에서 자주 보던 쿼리이다. 2번 쿼리가 조금 특이하다. 2번 쿼리는 1번 쿼리가 k번 적용되었을 때, 구간의 합을 구하는 쿼리이다. 그러면 1번 쿼리가 들어올 때마다 세그를 복사해서 하나 새로 만들면 되겠다. 그치만 N, M이 10만이기 때문에 어림도 없다.
1번 쿼리가 들어와도 세그트리의 오직 한 줄기만 바뀌는 것을 이용해보자. 이전 세그트리의 정보는 그대로 두고 새로 바뀌는 줄기만 추가로 붙여주면 된다. PST의 기본 개념을 바로 적용할 수 있는 문제였다.
이쁘게 잘 구현하자.
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct Node {
Node* l, * r;
ll val;
Node() { l = r = NULL; val = 0; }
};
Node* root[100010];
ll n, m, q, k, i, j, v;
ll a[100010];
ll r;
void init(Node* node, ll s, ll e) {
if (s == e) {
node->val = a[s];
return;
}
ll mid = (s + e) / 2;
node->l = new Node();
node->r = new Node();
init(node->l, s, mid);
init(node->r, mid + 1, e);
node->val = node->l->val + node->r->val;
}
void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
if (s == e) {
now->val = v;
return;
}
ll mid = (s + e) / 2;
if (x <= mid) {
now->l = new Node();
now->r = prv->r;
update(prv->l, now->l, s, mid, x, v);
}
else {
now->r = new Node();
now->l = prv->l;
update(prv->r, now->r, mid + 1, e, x, v);
}
now->val = now->l->val + now->r->val;
}
ll query(Node* node, ll s, ll e, ll l, ll r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return node->val;
ll mid = (s + e) / 2;
return query(node->l, s, mid, l, r) + query(node->r, mid + 1, e, l, r);
}
void solve() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 0; i < 100010; i++) root[i] = new Node();
init(root[r], 1, n); //root[0]에 첫 세그 저장
cin >> m;
while (m--) {
cin >> q;
if (q == 1) {
cin >> i >> v;
update(root[r], root[r + 1], 1, n, i, v);
r++;
}
else if (q == 2) {
cin >> k >> i >> j;
cout << query(root[k], 1, n, i, j) << endl;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
대충 수열과 쿼리 문제다.
쿼리는 어떤 [l, r] 구간 내에서 h값의 최대를 물어본다. 이 문제에서 h값이란 h 이상인 값의 개수가 h이상인 값 중 최댓값이다. 나는 이 쿼리에서 parametric search를 떠올렸다. 그런데 parametric search의 판정 부분을 어떻게 계산할지 감이 안 잡혔다. 여기서 djs100201에게 다음과 같은 아이디어를 배웠다. 현재 parametric search에서 k라는 수에 대해 판정하고 있다고 해보자. ([1, r] 구간에서 어떤 k이상의 값의 개수) - ( [1, l-1] 구간에서 어떤 k이상의 값의 개수) >= k이면 만족한다. (약간 누적합에서 구간합을 구하는 느낌이 나지 않는가? 아래의 문제들도 다 이 아이디어가 쓰인다 ㅋ)
그렇다면 우리는 모든 x(1 <=x <=n)에 대해 [1, x] 구간의 k이상인 값의 개수를 저장하고 있으면 쉽게 문제를 쉽게 해결할 수 있다. 그렇다면 n개의 세그먼트 트리를 만들면 기존에 풀던 플5 세그문제가 된다. 그치만 n이 20만이기 때문에, 절대 해결할 수 없다. 이때, [1, x] 구간과 [1, x+1] 구간의 세그트리의 다른 점을 살펴보자. 오직 하나의 값만 추가되기 때문에 세그트리에서 오직 한 줄기만 변경된다. 그러므로, PST를 이용하여 구현해주면 된다. 그렇다면 우리는 쉽게 [1, x] 구간에 k이상인 값의 개수를 구할 수 있고, 이를 통해 parametric search를 쉽게 진행할 수 있다.
잘 구현해주자.
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct Node {
Node* l, * r;
ll val;
Node() { l = r = NULL; val = 0; }
};
Node* root[200020];
ll n, q, l, r;
ll a[200020];
ll r_num;
void init(Node* node, ll s, ll e) {
if (s == e) {
node->val = 0;
return;
}
ll mid = (s + e) / 2;
node->l = new Node();
node->r = new Node();
init(node->l, s, mid);
init(node->r, mid + 1, e);
node->val = node->l->val + node->r->val;
}
void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
if (s == e) {
now->val = prv->val + v;
return;
}
ll mid = (s + e) / 2;
if (x <= mid) {
now->l = new Node();
now->r = prv->r;
update(prv->l, now->l, s, mid, x, v);
}
else {
now->r = new Node();
now->l = prv->l;
update(prv->r, now->r, mid + 1, e, x, v);
}
now->val = now->l->val + now->r->val;
}
ll query(Node* node, ll s, ll e, ll l, ll r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return node->val;
ll mid = (s + e) / 2;
return query(node->l, s, mid, l, r) + query(node->r, mid + 1, e, l, r);
}
bool chk(ll x, ll l, ll r) {//[l,r]에 x이상값이 x개 이상 있는지
ll j = query(root[r], 1, 200000, x, 200000);
ll i = query(root[l - 1], 1, 200000, x, 200000);
if (j - i >= x) return true;
else return false;
}
void solve() {
for (ll i = 0; i < 200020; i++) root[i] = new Node();
cin >> n >> q;
for (ll i = 1; i <= n; i++) cin >> a[i];
init(root[r_num], 1, 200000);
for (ll i = 1; i <= n; i++, r_num++) update(root[r_num], root[r_num + 1], 1, 200000, a[i], 1);
while (q--) {
cin >> l >> r;
ll low = 1;
ll high = 200000;
ll h = 1;
while (low <= high) {
ll mid = (low + high) / 2;
if (chk(mid, l, r)) {
low = mid + 1;
h = max(h, mid);
}
else high = mid - 1;
}
cout << h << endl;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
x축, y축, 1 사분면에 계란들이 있다. 쿼리마다 x, y축과 평행한 직사각형이 주어지면 그 안에 있는 계란의 수를 출력해야 한다. 모든 행마다 계란의 누적 개수를 저장하는 합세그를 만들어 관리하면 문제를 쉽게 해결할 수 있다. 예를 들어, 4~7행, 2~5열의 정보를 얻고 싶다면, (7행까지의 누적 2~5열 정보)에서 (3행까지의 누적 2~5열 정보)를 빼준다면 4~7행, 2~5열의 정보를 알 수 있다. 문제는 x값의 범위가 10의 5승이다. 세그먼트트리를 10의 5승 개 만들 수는 없다. 하지만 잘 생각해보면, x 헹궈 x+1행에서 변하는 세그먼트 값은 극히 적다. 그 부분만 잘 바꾸어 관리해주면 된다. 즉, Pesistent Segment Tree를 사용하면 된다. 이거 좌표들이 0부터 주어지는 거 주의하면서 잘 구현해주자.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct Node {
Node* l, * r;
ll val;
Node() { l = r = NULL; val = 0; }
};
Node* root[100002];
vector<ll> adj[100002];
ll n, m, x, y, l, r, b, t;
void init(Node* node, ll s, ll e) {
if (s == e) return;
ll mid = (s + e) / 2;
node->l = new Node();
node->r = new Node();
init(node->l, s, mid);
init(node->r, mid + 1, e);
node->val = node->l->val + node->r->val;
}
void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
if (s == e) {
now->val = prv->val + v;
return;
}
ll mid = (s + e) / 2;
if (x <= mid) {
now->l = new Node(); //이미 만들어져있으면 그대로 사용
now->r = prv->r;
update(prv->l, now->l, s, mid, x, v);
}
else {
now->r = new Node(); //안 만들어져 있는 경우에만 new Node()임
now->l = prv->l;
update(prv->r, now->r, mid + 1, e, x, v);
}
now->val = now->l->val + now->r->val;
}
ll query(Node* node, ll s, ll e, ll l, ll r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return node->val;
ll mid = (s + e) / 2;
return query(node->l, s, mid, l, r) + query(node->r, mid + 1, e, l, r);
}
void solve() {
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> x >> y;
x++;
y++;
adj[x].push_back(y);
}
for (ll i = 0; i <= 100001; i++) root[i] = new Node();
init(root[0], 1, 100001); //root[0]에 첫 세그 저장
vector<Node*> tmp;
tmp.push_back(root[0]);
for (ll i = 1; i <= 100001; i++) {
if (adj[i].empty()) root[i] = root[i - 1];
else {
for (auto y : adj[i]) {
Node* now = new Node();
update(tmp.back(), now, 1, 100001, y, 1);
tmp.push_back(now);
}
root[i] = tmp.back();
adj[i].clear();
}
}
ll ans = 0;
while (m--) {
cin >> b >> t >> l >> r;
b++;
t++;
l++;
r++;
ans += query(root[t], 1, 100001, l, r) - query(root[b - 1], 1, 100001, l, r);
}
cout << ans << endl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; cin >> tc;
while (tc--) solve();
}
부분 구간에서 k번째 수를 찾아야 한다.
만약 부분 구간이 아니라 전체 구간이 문제로 나왔다면 그냥 세그를 이용하여 문제를 해결하면 된다. 이런 문제를 세그 기본 문제에서 많이 풀어보았다. (boj.kr/2243)
그치만 이 문제는 쿼리마다 구간이 다 다르다.
원하는 구간의 정보를 얻고 싶다. 구간이 [l, r]로 주어졌다 해보자. 이때, [1, r] 구간의 정보가 반영된 세그트리에서 [1, l-1] 구간의 정보가 반영된 세그트리의 정보를 빼주면 [l, r] 구간의 정보를 알 수 있다. 누적합을 이용하여 합을 구하는 느낌과 비슷하다.
모든 x(1 <=x <=n)에 대해 [1, x] 구간의 정보를 갖고 있는 세그먼트 트리를 만들면 된다. 제한을 보면 당연히 세그먼트 트리를 N개 만들 수 없다! 그치만 잘 생각해보면 [1, x] 구간과 [1, x+1] 구간의 세그트리에서 변한 곳은 딱 한줄기뿐이다. 그곳만 따로 관리를 해주면 된다. 즉, Persistent Segment Tree를 사용하면 된다!
아 참고로, 값이 10^9까지 나오기 때문에 좌표압축이 필요하다. 마지막에 다시 출력할 때는 원래의 값을 출력해야 함을 잊지 말자! 대충 잘 구현해주자.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = int;
using pll = pair<ll, ll>;
struct Node {
Node* l, * r;
ll val;
Node() { l = r = NULL; val = 0; }
};
Node* root[100002];
vector<ll> x;
ll a[100002];
ll b[100002];
ll n, m, r, i, j, k;
void init(Node* node, ll s, ll e) {
if (s == e) {
node->val = 0;
return;
}
ll mid = (s + e) / 2;
node->l = new Node();
node->r = new Node();
init(node->l, s, mid);
init(node->r, mid + 1, e);
node->val = node->l->val + node->r->val;
}
void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
if (s == e) {
now->val = prv->val + v;
return;
}
ll mid = (s + e) / 2;
if (x <= mid) {
now->l = new Node();
now->r = prv->r;
update(prv->l, now->l, s, mid, x, v);
}
else {
now->r = new Node();
now->l = prv->l;
update(prv->r, now->r, mid + 1, e, x, v);
}
now->val = now->l->val + now->r->val;
}
ll query(Node* right, Node* left, ll s, ll e, ll k) {
if (s == e) return s;
ll d = right->l->val - left->l->val;
ll mid = (s + e) / 2;
if (d >= k) return query(right->l, left->l, s, mid, k);
else return query(right->r, left->r, mid + 1, e, k - d);
}
void solve() {
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
x.push_back(a[i]);
}
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
map<ll, ll> ma;
for (ll i = 1; i <= n; i++) {
ll tmp = a[i];
a[i] = 1 + (lower_bound(x.begin(), x.end(), a[i]) - x.begin());
ma[a[i]] = tmp;
}
ll p = x.size();
for (ll i = 0; i <= n; i++) root[i] = new Node();
init(root[r], 1, p);
for (ll i = 1; i <= n; i++, r++) update(root[r], root[r + 1], 1, p, a[i], 1);
while (m--) {
cin >> i >> j >> k;
cout << ma[query(root[j], root[i - 1], 1, p, k)] << endl;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
부분 수열 중에서 k보다 큰 원소의 개수를 출력하는 문제이다.
마찬가지로 전체 구간이라면 세그 기본문제이다. 또한, 쿼리의 수가 1이면 어렵지 않게 세그 2개를 구현하여 해결할 수 있다. 그치만 쿼리가 10만이다.
위 문제와 다른 점은 k번째 수를 찾는 것이 아니라 k보다 큰 원소의 개수를 찾는다는 것이다. 7469 문제를 이해하였다면 비슷한 방식으로 PST를 구현하여 해결해주면 된다는 것을 쉽게 알 수 있다. 잘 구현하자.
(13537이랑 13544는 다 같은데, 쿼리 조건이 조금 다르다. 수열과 쿼리3 문제의 쿼리 조건이 좀 특이한데, 오프라인 쿼리를 통해 해결할 수 없게 하려고 만들어진 조건인 것 같다. 나는 둘 다 PST로 해결했기 때문에, 코드가 동일하다고 보면 된다. 아래 코드는 수쿼3 코드다. xor 하는 거만 빼면 수쿼1 코드랑 같다.)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = int;
using pll = pair<ll, ll>;
struct Node {
Node* l, * r;
ll val;
Node() { l = r = NULL; val = 0; }
};
Node* root[100010];
vector<ll> x;
ll a[100010];
ll n, m, r, i, j, k;
void init(Node* node, ll s, ll e) {
if (s == e) {
node->val = 0;
return;
}
ll mid = (s + e) / 2;
node->l = new Node();
node->r = new Node();
init(node->l, s, mid);
init(node->r, mid + 1, e);
node->val = node->l->val + node->r->val;
}
void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
if (s == e) {
now->val = prv->val + v;
return;
}
ll mid = (s + e) / 2;
if (x <= mid) {
now->l = new Node();
now->r = prv->r;
update(prv->l, now->l, s, mid, x, v);
}
else {
now->r = new Node();
now->l = prv->l;
update(prv->r, now->r, mid + 1, e, x, v);
}
now->val = now->l->val + now->r->val;
}
ll query(Node* node, ll s, ll e, ll l, ll r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return node->val;
ll mid = (s + e) / 2;
return query(node->l, s, mid, l, r) + query(node->r, mid + 1, e, l, r);
}
void solve() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
x.push_back(a[i]);
}
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for (ll i = 1; i <= n; i++) a[i] = 1 + (lower_bound(x.begin(), x.end(), a[i]) - x.begin());
ll p = x.size() + 1;
for (ll i = 0; i <= n; i++) root[i] = new Node();
init(root[r], 1, p);
for (ll i = 1; i <= n; i++, r++) update(root[r], root[r + 1], 1, p, a[i], 1);
ll bef = 0;
cin >> m;
while (m--) {
cin >> i >> j >> k;
i ^= bef;
j ^= bef;
k ^= bef;
k = upper_bound(x.begin(), x.end(), k) - x.begin();
//cout << k << endl;
bef = query(root[j], 1, p, k + 1, p) - query(root[i - 1], 1, p, k + 1, p);
cout << bef << endl;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
boj.kr/8121 Step Traversing a Tree
굉장히 재밌게 풀었던 문제! 안 풀었으면 한 번 풀어보는 것을 추천한다. 나의 Funny Platinum 문제집에 추가되었다. (홍보 ㅋㅋ) Ibory라는 분이 추천해 주셨다.
트리가 주어진다. 모든 점을 한 번씩만 방문해야 한다. 이때, 방금 방문했던 점과 거리가 3 이하인 점만 방문해야 한다.
처음엔 이러한 생각을 했다. 어떤 줄기를 타고 내려갈 때, 한 칸씩 비워두면서 내려가고, 그 비워둔 칸을 타고 올라오면 될 것 같았다. 대충 아래 사진처럼.
근데 모든 트리가 이렇게 한 줄로 되어있지는 않다.
그치만 재귀로 dfs를 구현하면 한 줄기를 모두 다 본 뒤에 옆 줄기로 넘어가는 것을 알 수 있다. 오? 그러면 저 방식대로 구현을 진행하면 알아서 될 것 같았다. 옆 줄기로 넘어갈 때는 거리가 2 or 3이므로, 문제의 조건을 만족한다. 아 이래서 거리가 '3'이하가 되게 이동해야 한다고 주어진거구나! 라는 생각을 했다.
코드 짜기 전에 아래와 같은 트리 하나를 그려본 뒤, 확신이 생겼고 구현했다. 1번에 맞았다.
dfs 코드는 다음과 같이 짰다.
x는 항상 0 아니면 1을 가진다. 아래 그림에서 초록 부분이면 x가 1, 노란 부분이면 x가 0이다.
출력하는 위치를 잘 생각해보면 된다.
void dfs(ll now, ll par, ll x) {
if (x) cout << now << endl;
for (ll nxt : adj[now]) {
if (nxt == par) continue;
dfs(nxt, now, (x + 1) % 2);
}
if (!x) cout << now << endl;
}
전체 코드
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, u, v;
vector<ll> adj[5050];
void dfs(ll now, ll par, ll x) {
if (x) cout << now << endl;
for (ll nxt : adj[now]) {
if (nxt == par) continue;
dfs(nxt, now, (x + 1) % 2);
}
if (!x) cout << now << endl;
}
void solve() {
cin >> n;
for (ll i = 1; i <= n - 1; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0, 1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
boj.kr/23382 Hamiltooonian Hike
위 문제를 풀었더니 Ibory님께서 이 문제를 풀러 가라고 하셨다.
읽어보니 8121과 같은 문제인데, 이 문제는 트리가 아니었다. 그치만 모든 점이 연결되어 있어서 그냥 그래프에서 몇 개의 간선을 잘라내어 트리를 만들면 위 문제와 같다는 것을 발견했다. 위 문제의 코드에 방문처리만 잘~ 해주면 된다.
바로 구현했고 맞았다!
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m, u, v;
vector<ll> adj[200020];
ll visited[200020];
void dfs(ll now, ll par, ll x) {
visited[now] = 1;
if (x) cout << now << endl;
for (ll nxt : adj[now]) {
if (nxt == par) continue;
if (!visited[nxt]) dfs(nxt, now, (x + 1) % 2);
}
if (!x) cout << now << endl;
}
void solve() {
cin >> n >> m;
for (ll i = 1; i <= m; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0, 1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
여러 오렌지 선생님들께 감사합니다.
내일은 팀 연습을 하는 날이다. 기분이 나쁘지 않다면 후기를 써보지 않을까 싶다!
청정수컵 개최 후기도 기억이 희미해지기 전에 슬슬 쓸 생각이다.
'PS > 일지' 카테고리의 다른 글
| Hi, so to me seems like a notorious coincidence. (2) | 2022.10.28 |
|---|---|
| 5/24 PS일지 (9) | 2022.05.24 |
| 5/23 PS일지 (9) | 2022.05.23 |