Segment_Tree

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30880 🧐 관찰 및 접근 # 누가봐도 세그먼트트리 세팅인것같다. 금광같은거죠 노드 정의를 어떻게 하면 좋을까? 부분열이니까, R / O / C / K 개수는 당연히 있어야하고.. ROCK 개수는 ROCK개수 + 왼쪽 R + 오른쪽 OCK, RO + CK, ROC + K,, 아하, R / RO / ROC / ROCK / O / OC / OCK / C / CK / K 다 세면 되나? 아 그런데, ROCK의 개수를 세는게 아니라 ROCK로 끝나는 문자열의 개수를 세야한다는건, 길이도 어떻게 잘 곱해야되는것같은데 $XRRX$ 와 $XOCK$ 를 합친다고 생각해보자. 답은 $XRROCK, XROCK, XROCK, RROCK, ROCK, ROCK$로 6개인것 같다. 뒤에 $OCK$근처에서는 별 감흥이 없는 것 같고, 앞에있는 $R$들에 대해서만 상관이 있는 것 같다. 그 위치들에 대해, $2 + 4$ 해서 6이 나온 것 같다. 노드 안에서 $R$에 대해, $R$의 개수가 아니라 $R$로 끝나는 부분 문자열의 개수를 저장하는게 좋겠다. R, RO, ROC, ROCK에 대해서 그렇게 해주면 충분하다! 💻 풀이 # 코드 (C++): struct Node{ mint R = 0, RO = 0, ROC = 0, ROCK = 0, O = 0, OC = 0, OCK = 0, C = 0, CK = 0, K = 0; mint len = 0; mint ans = 0; Node(){}; Node(char c){ if(c == 'R') R += 1; if(c == 'O') O += 1; if(c == 'C') C += 1; if(c == 'K') K += 1; len = 1; }; }; Node pull(Node a, Node b){ Node ret; ret.R = a.R + mint(2).pow(a.len.val)*b.R; ret.O = a.O + b.O; ret.C = a.C + b.C; ret.K = a.K + b.K; ret.RO = a.RO + mint(2).pow(a.len.val)*b.RO + a.R*b.O; ret.OC = a.OC + b.OC + a.O*b.C; ret.CK = a.CK + b.CK + a.C*b.K; ret.ROC = a.ROC + mint(2).pow(a.len.val)*b.ROC + a.RO*b.C + a.R*b.OC; ret.OCK = a.OCK + b.OCK + a.OC*b.K + a.O*b.CK; ret.ROCK = a.ROCK + mint(2).pow(a.len.val)*b.ROCK + a.ROC*b.K + a.RO*b.CK + a.R*b.OCK; ret.len = a.len + b.len; return ret; } void solve(){ int N; cin >> N; string S; cin >> S; vector<Node> v(N); rep(i, 0, N) v[i] = Node(S[i]); SegmentTreeNode ST(N, v); int Q; cin >> Q; while(Q--){ int op; cin >> op; if(op == 1){ int idx; cin >> idx; char c; cin >> c; ST.set(idx-1, Node(c)); } else{ int l, r; cin >> l >> r; l--; r--; cout << ST.query(l, r).ROCK << '\n'; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14587 🧐 관찰 및 접근 # 전처리를 적당히 할 수 있을까? 이분탐색을 좀 하면서 밀면서 하면, 특정 도미노를 한쪽으로 밀었을때 어디까지 넘어가는지 할 수 있나? 아, min/max 세그먼트 트리로 되는거같다 마지막은 그리디가 아니라 DP로 해야한다! 아니근데 X가 정렬되어 주어지지 않는다;;;;; 그래도 구현이 막 어렵지 않은듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> X(N), H(N); vector<pll> dominos(N); rep(i, 0, N) cin >> dominos[i].first >> dominos[i].second; sort(all(dominos)); rep(i, 0, N){ X[i] = dominos[i].first; H[i] = dominos[i].second; } SegmentTreeMinMax ST_min(N), ST_max(N); // calc leftmost ST_min.set(0, 0); rep(i, 1, N){ ll val = X[i] - H[i]; auto idx = lower_bound(all(X), val) - X.begin(); auto Q = ST_min.query(idx, i-1); ST_min.set(i, min((ll)i, ST_min.query(idx, i-1).first)); } // calc rightmost ST_max.set(N-1, N-1); rrep(i, 0, N-1){ ll val = X[i] + H[i]; auto idx = upper_bound(all(X), val) - X.begin() - 1; auto Q = ST_min.query(i+1, idx); ST_max.set(i, max((ll)i, ST_max.query(i+1, idx).second)); } vector<int> DP(N, 1e9); DP[0] = 1; DP[ST_max.get_val(0)] = 1; rep(i, 1, N){ int lft = ST_min.get_val(i)-1; if(lft < 0) DP[i] = 1; else DP[i] = min(DP[i], DP[lft] + 1); int rht = ST_max.get_val(i); DP[rht] = min(DP[rht], DP[i-1] + 1); } cout << DP[N-1]; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5916 🧐 관찰 및 접근 # 트리가 주어진다. 두 정점 사이 경로에 1을 더한다. 두 정점 사이 경로의 가중치의 합을 계산한다. 나이브하게는 $O(QN)$이겠지만, HLD와 Lazy 세그먼트 트리를 이용해서 $O(Qlog^2N)$정도에 계산할 수 있을 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; Tree tree(N); rep(i, 0, N-1){ int u, v; cin >> u >> v; tree.add_edge(u, v); } tree.build(); LazySegmentTree seg(N+1); while(M--){ char op; cin >> op; int u, v; cin >> u >> v; if(op == 'P'){ vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) seg.update(L, R, 1); } else{ ll ans = 0; vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) ans += seg.query(L, R); cout << ans << '\n'; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/35288 🧐 관찰 및 접근 # 문제를 정리하면 다음과 같다. 트리가 주어진다. 간선을 $K$개 지워서 포레스트로 만든다. 포레스트를 잘 합쳐서 트리의 지름이 최소가 되도록 하자. 포레스트를 잘 합치는 문제는 빌라봉으로 유명하다. 이 문제에 따르면, 세개 이상의 트리를 합칠 때, 가장 긴 트리의 지름 세개를 $a \geq b \geq c$ 라고 하면 그 결과는 $\max(a, \lceil\frac{a}{2}\rceil + \lceil\frac{b}{2}\rceil + 1, \lceil\frac{b}{2}\rceil + \lceil\frac{c}{2}\rceil + 2)$ 결과는 위와 같고, 이는 새로 만든 간선을 $0, 1, 2$개 이용하는 경로중 가장 긴것과 같다. 그리디하게 가장 긴 지름의 중심에 다른 중심들을 이은 모양에서 나온 결과이다. 그렇다면 트리를 빠르게 쪼개서 지름만 빠르게 계산할 수 있으면 되는 것 같다. 이걸 어떻게 할 수 있을까? 예제 1번의 트리를 ETT를 하면서 그려보자. ![[Drawing 2026-02-25 22.49.23.excalidraw.png]] 그리고 세번째 쿼리를 생각해보자. $(1, 2), (3, 6), (4, 5, 7)$으로 나뉘어야 하는디… ETT로 생각하면, $(1, 2, (5, (3, 6), 4, 7))$ 같은 느낌으로 그룹지어지는건가? 잘 처리된 부분들은 상관 없는데, $(5, 4, 7)$같은데서 지름을 어떻게 구하면 좋을지 감이 안온다. 일단 저걸 $(5), (4,7)$ 두 덩어리를 합치는 연산으로 보자. 오일러 투어 테크닉을 적용하면 연속 구간에 속하는 노드들의 지름은 세그먼트 트리로 구할 수 있다고 한다. 이걸 어떻게 하는거지? 트리 두개의 지름의 양끝 점을 각각 $(a, b), (c, d)$ 라고 할때 두 트리를 합친곳에서의 지름은 $(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)$중에서 존재한다. 이를 pull연산으로 잘 정의해보자. 구현이 상당히 어렵다.. 💻 풀이 # 코드 (C++): void solve(){ int N, Q; cin >> N >> Q; vector<vector<int>> links(N+1); vector<pii> edges; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); edges.push_back({u, v}); } auto [ETT_in, ETT_out] = ETT(N, links); vector<int> ETT_inv(N+1); rep(i, 1, N+1) ETT_inv[ETT_in[i]] = i; LCA_Tree = new Tree_LCA(N+1, links); vector<Node> nodes(N+1); rep(i, 1, N+1) nodes[i] = Node(ETT_inv[i], ETT_inv[i], 0); SegmentTreeNode seg(N+1, nodes); vector<int> edge_to_subtree(N-1); rep(i, 0, N-1){ auto [u, v] = edges[i]; if(LCA_Tree->depth[u] < LCA_Tree->depth[v]) swap(u, v); edge_to_subtree[i] = u; } while(Q--){ int K; cin >> K; vector<int> cuts(K); rep(i, 0, K) cin >> cuts[i]; vector<Node> Query_nodes; vector<pair<int, bool>> events; // {ETT_idx, is_end} for(auto c: cuts){ int u = edge_to_subtree[c-1]; events.push_back({ETT_in[u], false}); events.push_back({ETT_out[u], true}); } sort(all(events)); int cur = 1; stack<Node> stk; stk.push(Node()); for(auto [idx, is_end]: events){ if(is_end){ Node& top = stk.top(); top = seg.pull(top, seg.query(cur, idx)); cur = idx+1; Query_nodes.push_back(top); stk.pop(); } else{ Node& top = stk.top(); top = seg.pull(top, seg.query(cur, idx-1)); cur = idx; stk.push(Node()); } } Node& top = stk.top(); top = seg.pull(top, seg.query(cur, N)); Query_nodes.push_back(top); sort(all(Query_nodes), [](Node a, Node b){ return a.dist > b.dist; }); int ans = 0; if(Query_nodes.size() > 0) ans = Query_nodes[0].dist; if(Query_nodes.size() > 1) ans = max(ans, (Query_nodes[0].dist+1)/2 + (Query_nodes[1].dist+1)/2 + 1); if(Query_nodes.size() > 2) ans = max(ans, (Query_nodes[1].dist+1)/2 + (Query_nodes[2].dist+1)/2 + 2); cout << ans << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/9345 🧐 관찰 및 접근 # 수열에서의 swap연산이 주어지고, 수열의 $L, R$ 범위가 주어졌을 때 해당 범위에 $L \leq x \leq R$의 모든 수가 있는지 묻는 문제이다. 합같은것으로는 저걸 구분할 수가 없다. $(3, 4)$나 $(2, 5)$나 같으니까. 아하, DVD들끼리 겹치지 않으므로 구간 최소/최댓값을 이용하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pii> a(N); rep(i, 0, N) a[i] = {i, i}; SegmentTree ST(N, a); while(K--){ int op, a, b; cin >> op >> a >> b; if(op == 0){ int aval = ST.query(a, a).first; int bval = ST.query(b, b).first; ST.set(a, bval); ST.set(b, aval); } else{ pii res = ST.query(a, b); if(res.first == a && res.second == b) cout << "YES\n"; else cout << "NO\n"; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2042 🧐 관찰 및 접근 # 자명한 세그먼트 트리 연습 문제이다. 기본적으로 업데이트가 없이 구간의 합을 구해야 한다면, 이는 누적합으로 빠르게 해결할 수 있다. 이때 합을 구하는 쿼리는 $O(1)$, 업데이트는 $O(N)$이다. 업데이트를 빠르게 하기 위해선, 합을 나이브하게 구하는 방법이 있겠다. 이때 합을 구하는 쿼리는 $O(N)$, 업데이트는 $O(1)$이다. 버킷을 잘 나누어서, 두 방법의 이득만을 취하면 제곱근 분할법을 이용해서 $O(Q\sqrt{N})$까지 줄일 수 있고, 해당 문제에서는 $N \leq 10^6$이므로 약 2천만정도에 바운드된다. 지금과 같이 두 노드를 합치는 것이 직관적이고 용이할 경우에는 세그먼트 트리를 쓸 수 있으며, 두 노드를 이용해 역원과 역연산을 정의할 수 있는 경우 펜윅트리도 이용할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; SegmentTreeSum ST(N); rep(i, 0, N){ ll x; cin >> x; ST.set(i, x); } ST.build(); rep(i, 0, M+K){ ll a, b, c; cin >> a >> b >> c; if(a == 1) ST.update(b-1, c - ST.query(b-1, b-1)); else cout << ST.query(b-1, c-1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10868 🧐 관찰 및 접근 # 구간 최솟값을 $M$번 구하는 문제이다. 구간합은 누적합 배열을 이용해서 $O(1)$에 구할 수 있다. 하지만 구간 최솟값은 역원과 역연산이 없기에, 누적 최솟값 배열을 이용하기 곤란하다. 세그먼트 트리를 이용해서 구간 $O(logN)$개의 구간만을 관리하는 방법으로 풀 수 있겠다. 하지만, 업데이트가 없는 경우 희소 배열을 이용해서 $O(1)$에 구할 수 있음이 알려져있다. 💻 풀이 # 코드 (C++): struct RMQ{ // Range Minimum Query int N, H; vector<vector<int>> table; RMQ(int N, vector<int> &arr): N(N){ H = 1; while((1 << H) <= N) H++; table.assign(N, vector<int>(H)); rep(i, 0, N) table[i][0] = arr[i]; rep(j, 1, H) rep(i, 0, N){ int right = i + (1 << (j-1)); if(right < N) table[i][j] = min(table[i][j-1], table[right][j-1]); else table[i][j] = table[i][j-1]; } } int query(int l, int r){ // [L, R] r++; int k = 31 - __builtin_clz(r-l); return min(table[l][k], table[r-(1 << k)][k]); } }; void solve(){ int N, M; N = getu<6, int>(); M = getu<6, int>(); vector<int> A(N); rep(i, 0, N) A[i] = getu<10, int>(); RMQ rmq(N, A); while(M--){ int l, r; l = getu<6, int>(); r = getu<6, int>(); putu<10, int>(rmq.query(l-1, r-1)); } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16225 🧐 관찰 및 접근 # 약간 게임이론적이네. $(A_i, B_i), (A_j, B_j)$ 두가지를 고른다. 이때, $B_i > B_j$라면 $A_j$, $B_i < B_j$라면 $A_i$를 얻게된다. 직관적인것들을 생각해보자. $A_i$가 크고, $B_i$가 작은것들이 있으면 좋겠다. 위 친구들을 $A_i$가 작거, $B_i$가 큰 친구들이랑 매칭시켜서 없애버리면 좋다. $B$가 가장 작은 문제는 언제나 내가 풀게 된다. $B$가 가장 큰 문제는 언제나 상대가 풀게 된다. 이쪽에서 출발해볼까? $B$에 대한 오름차순으로 정렬해보자. 그러면 버릴 문제를 하나 고를 수 있다. 일단 예제를 $B$에 대한 오름차순으로 정렬한 후, $A$만 남기면 $(2, 4, 8, 6)$ 이 된다. 이때 2를 택하고 4를 버려고, 8을 택하고 6을 버리면 10이 된다. 여러개로 생각해보니, 약간 올바른 괄호 문자열 맛으로 되는데… 20만 $O(N^3)$ DP는 안된다이 $\text{DP}[i][j]$: $i$번째까지 봤을때, 여는괄호가 $j$개일때 최댓값 이라고 하면 $O(N^2)$도 된다만… 근데 열리는 괄호는, 생각보다 빠르게 열어줘야한다. 1번을 먹었으니, $(2, 3)$중에 하나는 무조건 열어야 한다. $2$를 먹었다면, $3, 4, 5$중 하나는 무조건 열어야 한다. $3$을 먹었다면, $2, 4, 5$중 하나는 무조건 먹어야 한다. $k$개 먹었다면, $2 \leq i \leq 2*k + 1$ 범위 내에서 한개를 더 먹어줘야한다. 이때 최댓값을 먹어줘야하고, 점 업데이트가 있으니 세그먼트 트리로 되겠다. 세그워킹 ㄱ.ㄱ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> A(N); rep(i, 0, N) cin >> A[i].first; rep(i, 0, N) cin >> A[i].second; sort(all(A), [](pii a, pii b){ return a.second < b.second; }); vector<ll> v; rep(i, 0, N) v.push_back(A[i].first); ST.init(N); rep(i, 0, N) ST.set(i, v[i]); ST.build(); ll ans = v[0]; rep(i, 1, N/2){ auto [val, idx] = ST.seg_walk(1, i*2); ans += val; ST.update(idx, 0); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31055 번역 문제 번역 # Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요! 연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). 그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다:

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12858 🧐 관찰 및 접근 # $\text{gcd}(n, n+1)$은 몇일까? $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자. 이때 $p$는 간격 $p$마다 한개씩 존재한다. $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다. 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다! 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다. 같은 방법으로, $\text{gcd}(a, b) = \text{gcd}(a, b-a)$ 임도 알 수 있다. 유클리드 호제법에서도 알 수 있듯이! 구간 쿼리지만, Lazy하게 연산하기는 쉽지 않아보인다. 하지만 $\text{gcd}(x_a, x_{a+1}, x_{a+2}, \dots, x_b)$ 를 $\text{gcd}(x_a, x_{a+2} - x_{a+1}, x_{a+3} - x_{a+2}, \dots, x_b - x_{b-1})$ 이라고 생각하면, 바뀌는 수는 생각보다 많지 않다! Lazy한 합 연산과 최대공약수에 대한 그냥 세그먼트 트리로 풀 수 있지 않을까? 사실 Lazy부분도 구간 덧셈, 점 쿼리이므로 그냥 세그로 바꿀 수 있지만, 귀찮으니까 ㅋㅋ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; LazySegmentTree LST(N); ST.init(N-1); vector<ll> A(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) LST.set(i, A[i]); LST.build(); rep(i, 0, N-1) ST.set(i, abs(A[i+1] - A[i])); ST.build(); int Q; cin >> Q; while(Q--){ ll op, a, b; cin >> op >> a >> b; a--; b--; if(op){ LST.update(a, b, op); if(a-1 >= 0) ST.update(a-1, abs(LST.query(a-1, a-1) - LST.query(a, a))); if(a+1 < N) ST.update(a, abs(LST.query(a+1, a+1) - LST.query(a, a))); }else{ cout << gcd(LST.query(a, a), ST.query(a, b-1)) << '\n'; } } } 🔒 구현 코드 잠금