Sparse_Table

📝 문제 정보 # 링크: 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/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/17435 🧐 관찰 및 접근 # 함수 $f$가 주어질 때, 최대 $500\,000$번 합성한 값을 구해야 한다. 나이브하게 계산하면 $O(QN)$으로 시간초과다. 전체를 전처리해두기엔, 공간복잡도가 $O(mN)$으로 너무 커진다. 따라서 적당히 전처리를 해두자. 이는 LCA에서 했던것과 같이, 희소 배열로 가능할 것 같다. 각 정의역에 대해 $1$번, $2$번, $4$번, $\cdots 2^k$번 합성한 결과를 저장해서 쿼리를 처리하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> f(20, vector<int>(N+1)); rep(i, 1, N+1) cin >> f[0][i]; rep(k, 1, 20) rep(i, 1, N+1) f[k][i] = f[k-1][f[k-1][i]]; int Q; cin >> Q; while(Q--){ int n, x; cin >> n >> x; rep(k, 0, 20) if(n & (1 << k)) x = f[k][x]; cout << x << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12008 🧐 관찰 및 접근 # 흠, 결국 마지막에 사용한 모든 숫자들은 하나의 범위로 나타날 것 같다. 범위를 쪼개는 맛의 DP를 할 수 있나? $\text{DP}[i][j]$: $i$~$j$까지의 숫자를 모두 사용해서 만들어진 수 라고 하면 $O(N^2)$의 시간이 걸린다… 이런 느낌으로 $\log$로 바운드 시킬 수 있q을까? $(1, 1, 1, 2)$ 에서 1들을 2로 묶을 수 있는 경우를 각 인덱스에 대해서 표시 $(2, 1, 2), (1, 2, 2)$ 등으로 나타내져을때, 2들을 4로 묶을 수 있는 경우에 대해 표시.. 그러니까, $(1, 1, 1, 2)$는 2로 묶었을때 다음 인덱스는 $(1, 2, -1, 3)$ 처럼 (0-based) 그러면 뒤로 계속 폴짝폴짝 뛰어다니면서 계산하면, 만들 수 있는 최대값인 58에 대해 $O(N)$번 하면 될거같기도..? 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<vector<int>> v(60, vector<int>(N+1, -1)); rep(i, 0, N) v[A[i]][i] = i; int ans = 0; rep(b, 0, 60){ rep(i, 0, N) if(v[b][i] != -1 && v[b][v[b][i]+1] != -1) v[b+1][i] = v[b][v[b][i]+1]; rep(i, 0, N) if(v[b][i] != -1) ans = max(ans, b); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3176 🧐 관찰 및 접근 # 도로가 N-1개인걸 보니 트리겠구만 이때 경로상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하라는데… HLD를 써도 되지만, sparse table에서의 RMQ처리처럼 진행해도 큰 문제가 없겠다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } dfs(1, -1, 0); rep(j, 1, 20) rep(i, 1, N+1) if(par[i][j-1]){ par[i][j] = par[par[i][j-1]][j-1]; mnDist[i][j] = min(mnDist[i][j-1], mnDist[par[i][j-1]][j-1]); mxDist[i][j] = max(mxDist[i][j-1], mxDist[par[i][j-1]][j-1]); } int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; auto [mn, mx] = calc(u, v); cout << mn << ' ' << mx << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1761 🧐 관찰 및 접근 # 트리에서, 두 정점 사이의 경로는 유일하다. 해당 경로는 두 정점의 LCA를 지난다. 두 점 사이의 거리는 $d(u) + d(v) - 2*d(\text{LCA}(u, v))$로 계산할 수 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int _par){ for(auto [nxt, w]: links[cur]){ if(nxt == _par) continue; dist[nxt] = dist[cur] + w; depth[nxt] = depth[cur] + 1; par[nxt][0] = cur; dfs(nxt, cur); } } int LCA(int u, int v){ if(u == v) return u; if(depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; rep(i, 0, 16) if((diff >> i) & 1) u = par[u][i]; if(u == v) return u; rrep(i, 16, 0){ if(par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } return par[u][0]; } ll getDist(int u, int v){ int lca = LCA(u, v); return dist[u] + dist[v] - 2 * dist[lca]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } dfs(1, -1); rep(j, 1, 16) rep(i, 1, N+1) par[i][j] = par[par[i][j-1]][j-1]; cin >> Q; while(Q--){ int u, v; cin >> u >> v; cout << getDist(u, v) << '\n'; } } 🔒 구현 코드 잠금