📝 문제 정보 # 링크: 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/16964 🧐 관찰 및 접근 # dfs를 돌리듯이 지금까지 걸어온 과정들을 기록하면서 다음 노드를 갈 수 있었는가?를 체크하자. 💻 풀이 # 코드 (C++): import sys input = sys.stdin.readline N = int(input()) links = [set() for _ in range(N + 1)] for _ in range(N-1): a, b = map(int, input().split()) links[a].add(b) links[b].add(a) lst = list(map(int, input().split())) if lst[0] != 1: print(0) exit() nidx = 1 stk = [1] while nidx < N: if not stk: print(0) exit() cur = stk[-1] if lst[nidx] in links[cur]: stk.append(lst[nidx]) nidx += 1 else: stk.pop() print(1) 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16940 🧐 관찰 및 접근 # 풀이1 문제 그대로 큐에 넣으면서 시뮬레이션해볼 수 있겠다. 같은 레벨 안에서 원하는대로 선택할 수 있으니, 다음으로 들려야하는걸 셋으로 잘 관리하면서 해보자. 풀이2 현재 내가 있는 노드, 그리고 다음 노드를 큐에 넣을 수 있는지를 체크하는 노드 두가지로 문제를 시뮬레이션하자. cidx에서 nidx로 갈 수 있으면 nidx++를 하고, 없을때 cidx를 ++하자. nidx가 N에 닿지 못했다면 불가능한 것이다. 이 풀이는 트리가 아닌 그래프에서만 가능하다! 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> links(N+1); rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } vector<int> order(N); bitset<100001> visited; rep(i, 0, N) cin >> order[i]; queue<set<int>> v; v.push({1}); visited[1] = true; int idx = 0; while(idx < N){ set<int> nset; while(!v.empty() && v.front().empty()) v.pop(); if(v.empty()){ cout << 0; return; } if(v.front().count(order[idx]) == 0){ cout << 0; return; } int cur = order[idx]; v.front().erase(cur); for(int nxt: links[cur]){ if(visited[nxt]) continue; visited[nxt] = true; nset.insert(nxt); } v.push(nset); idx++; } cout << 1; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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를 하면서 그려보자. 그리고 세번째 쿼리를 생각해보자. $(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/2803 🧐 관찰 및 접근 # 비트마스킹적으로 접근해보면, 여러 장난감 상자들의 or 연산결과가 $1111111..$이 되도록 하는 조합의 개수를 찾으면 되는 것 같다. $N$에 대해 생각하긴 까다로우므로, $M \leq 20$인 것을 이용해서 $M$에 대한 비트마스킹된 상자의 수로 생각해보자. 이후 과정을 포함배제로 진행하면 $O(2^N \times 2^N)$이겠지만, 우리는 SOS DP를 이용해서 $O(N2^N)$ 에 계산할 수 있음을 알 수 있다. 그런데 그냥 기본적인 SOS DP랑은 세팅이 조금 다른가? 고민해보자. 기본적인 SOS DP는 해당 비트마스크의 부분집합의 원소 개수의 합이다. 이번에 구해야하는건 해당 비트마스크를 만들어줄 수 있는 조합의 개수인데.. 결국 어떤 상자 $110011$을 골랐다고 생각해보자. 그러면, $??11??$ 인걸 모두 고르면 된다. 이걸 부분집합으로 세긴 힘들지만, 뒤집어서 생각한다면 $??00??$을 찾는 것이고, 이건 $110011$의 부분집합의 개수와 같은 것 같다! 자기 자신을 세지 않도록 조심하자. 그런데 저 방법으로 세면, 두개의 or연산밖에 고려하지 못한다… 3개 이상인걸 고려하려면 DP 설계를 조금 더 잘해야 할 것 같다. 아하, 원래게 $??11??$인 개수를 안다면, 여기에서 한개 이상만 고르면 된다. 그 개수를 $\text{cnt}$라고 하면, $2^{\text{cnt}} - 1$이 성립하는거 같기도? 근데 다시 생각해보니, 뭐랄까 원래가 $??10??$$ 인거랑 $??01??$$ 인거랑이 합쳐져서 되는것들을 못세는거..같기도? 연산해서 $11$을 만들기 위해선, $(11 + 10 + 01 + 00)^2$ 같은 느낌으로 생각해보자. 저 연산 결과는 $$ 11^2 + 10^2 + 01^2 + 00^2 + \\ 2(11\cdot10 + 11\cdot01 + 11\cdot00 + 10\cdot01 + 10\cdot00 + 01\cdot00) $$ 이고, 잘 고민해보니 $11$의 부분집합의 제곱 - $11, 01$의 부분집합의 제곱 - $00$의 부분집합의 제곱을 하면 깔끔하게 $11^2 + 2(11\times10 + 11\times01 + 11\times00 + 10\times01)$이 된다. 아니 잠깐만, 저 느낌을 그대로 가져가면 그냥 부분집합의 합으로 SOS DP를 한다음에 포함배제를 때려버리면 어떻게든 된다. 연산결과가 $11...11$인놈들 - $(01...11), (10..111)...$ + $...$ 이렇게 하면 되는구나! 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<int> A(N); rep(i, 0, N){ int K; cin >> K; int ret = 0; rep(j, 0, K){ int x; cin >> x; ret |= (1 << (x-1)); } A[i] = ret; } vector<int> SOS(1 << M, 0); for(auto x: A) SOS[x] += 1; rep(i, 0, M) rep(mask, 0, 1<<M) if(mask & (1 << i)) SOS[mask] += SOS[mask^(1<<i)]; mint ans = 0; rep(mask, 0, 1<<M){ int cnt = 0; rep(i, 0, M) if((mask & (1 << i)) == 0) cnt++; if(cnt & 1) ans -= (mint(2).pow(SOS[mask])); else ans += (mint(2).pow(SOS[mask])); } cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17364 🧐 관찰 및 접근 # 어… 문제가 상당히 곤란해보인다. ㅋㅋㅋㅋ 첫번째 예제부터 친절해서 망정이지, 저런거 없었으면 당연히 1357번 1등한테 먹이고 3 출력했을 것 같다. $K = 1$일때부터 풀어보자. 이때는 자명하게도 회의실 배정 문제와 같다. 끝나는 시간을 기준으로 정렬하고, 그리디하게 가져가자. $K = 2$라면? 형섭이는 1등이 먹고 남은 대회들에 대해서, 결국 위의 그리디한 방법으로 가져갈 것이다. 이 때, 1등이 1, 3, 5, 7번 대회를 가져가서 남은 대회가 $(2, 3), (4, 5), (6, 7)$ 이라면 3개를 먹는 것이고, 1, 4, 7번째 대회를 가져가서 남은 대회가 $(2, 3), (3, 4), (5, 6), (6, 7)$ 이라면 2개밖에 못먹는 것이다. 이걸 DP같은걸로 어떻게 잘 가져가면 좋을것같은데.. 엥? 근데 이거 약간 그리디하게 되지 않을까? 형섭씨도 그리디하게 먹으려고 하니, 형섭씨의 그리디를 의도적으로 방해하자. 제일처음에 시간은 $T = 0$일때, 형섭씨는 첫번째 대회 $(1, 2)$를 출전하려고 한다. 바아로 1등 출동 힝잉잉거리면서 두번째 대회 $(2, 3)$을 출전하려고 한다. 이걸 막을수는 없다. 그런데 이걸 나가고 나면 $(3, 4)$ 까지는 못나가시니 절대 안막아버리기 그다음에 $(4, 5)$ 대회를 나가시려고하면, 이때 첫번째 대회 나가신분은 퇴근 후 집에서 요양중이시다. 바로 저기 보내버리자. 다시 형섭씨는 힝잉잉거리면서.. 어쩌구 우선순위 큐로 관리하면서 그리디하게 진행할 수 있을 것 같다!!!!!!! ㅠ.ㅠ 바로 틀렸다. 이것만으로는 상대방이 너무 많은 대회를 나갈 수 있는 것 처럼 된다. 아하, $(3, 5), (4, 5), (2, 7)$이 있다고 해보자. 단순하게 끝나는 시간만 관리해서는, 5일에 나와서 퇴근 후 저 $(2, 7)$ 대회에 나갈 수 있는것처럼 내가 해버렸다. 이러면 안되지 음.. 어차피 세개 다 무조건 못먹는건 맞는데. 그리디라고 생각하면.. 쓸 수 있는 놈중 가장 마지막에 끝나는 놈을 쓰는게 유효한가? 다음 $(s, e)$에서 어차피 $e$는 꽤 크고, $s$가 빠른 놈이 들어오는게 문제인 것 같은데, 그러면 자유로운 친구가 더 오래 쉬도록 해야하는거 같다 .그러면 맞는거같다!! 셋같은걸로 지점을 잘 찾아보자. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pii> contests(N); rep(i, 0, N) cin >> contests[i].first >> contests[i].second; sort(all(contests), [](const pii &a, const pii &b){ if(a.second == b.second) return a.first < b.first; return a.second < b.second; }); int ans = 0; int T = 0; multiset<int> st; rep(i, 0, K-1) st.insert(0); for(auto &[a, b]: contests){ if(a <= T) continue; auto it = st.lower_bound(a); if(it == st.begin()){ ans++; T = b; continue; } it--; st.erase(it); st.insert(b); } cout << ans; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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/34088 🧐 관찰 및 접근 # $K$로 나눈 나머지가 같다 = 고른 부분집합의 원소들의 차이가 모두 $K$의 배수이다. 그러면? 분위기상 소수만? 신경써도 되는거같다. 근데 숫자들의 차이가 $10^9$까지인데… 그러면 너무 많은데 흠 근데 일단 직관적으로, $K = 2$일때 비둘기집의 원리에 의해 답은 ${N/2}$ 이상이긴 하다. 그리고 직관적으로, 웬만한 경우에 $K$가 작을때 답이 있을 것 같다. $K$가 클때를 억지로 만들 수 있나? $K > 1000$ 쯤듸는 어떤 소수라고 하면, 억지로 만들 수 있는 것 같긴 하다. 그런데, 이때 $K$가 $N/2$개 이상의 부분집합에 대해 나머지가 같아야하므로, 다르게 말하면 어떤 두 수를 뽑앗을때 50% 이상의 확률로 $K$는 해당 수의 약수이다. 랜덤으로 풀 수 있지 않을까? 💻 풀이 # 코드 (C++): void solve(){ auto start = chrono::high_resolution_clock::now(); bitset<32000> isPrime; isPrime.set(); isPrime[0] = isPrime[1] = 0; rep(i, 2, 32000) if(isPrime[i]){ for(ll j = (ll)i*i; j < 32000; j += i) isPrime[j] = 0; } vector<int> primes; rep(i, 2, 32000) if(isPrime[i]) primes.push_back(i); int N; cin >> N; vector<ll> A(N); rep(i, 0, N) cin >> A[i]; int ans = (N+1)/2; while(1){ auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start); if(duration.count() > 900) break; int a = rand() % N, b = rand() % N; int diff = abs(A[a] - A[b]); vector<int> divs; for(int p: primes){ if(p*p > diff) break; if(diff % p == 0){ divs.push_back(p); while(diff % p == 0) diff /= p; } } if(diff > 1) divs.push_back(diff); for(int d: divs){ map<int, int> mp; for(auto x: A) mp[x%d]++; for(auto [_, c]: mp) ans = max(ans, c); } } cout << ans; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25563 🧐 관찰 및 접근 # 일단 세개를 따로 구하면 되는 것 같다. XOR이 제일 쉬워보인다. XOR은 역연산이 존재하므로, $A_i \oplus A_j = K$를 만족하는 $A_j$는 $A_i \oplus K$로 구할 수 있다. $A_i \leq 1\,000\,000$이므로 그냥 구하면 될듯. 양쪽에서 구했으니 2로 나누는것만 조심하면 되겠다. $K = 0$일때를 주의하자. AND를 다음으로 봐보자. $A_i, A_j$ 모두 $K$와 and연산한 결과는 $K$여야 한다. 그리고 $A_i - K, A_j - K$는 and 연산한 결과가 $0$이어야 한다. 숫자 $N$개에서 두 수의 and 결과가 $0$인 조합 개수를 빠르게 구할수가 있나? 이 같은 아이디어로 OR도 해결할 수 있는 것 같으니, 이걸 고민해보자. 약간 포함배제같은맛으로 될라나? 일단 쉽게 $A_i$에서 $k$번째 비트 하나가 켜져있다고 해보자. 그러면 나머지들에서 $k$번째 비트가 꺼져있기만 하면 된다. 이건 뭐 $k$번째 비트가 켜져있는 / 꺼져있는 집합으로 하면 될틴데,… $A_i$에서 $k_1, k_2$번째 비트 두개가 켜져있다고 해보자. 이번에는 나머지들에서 $k_1, k_2$ 번째 비트 모두가 꺼져있어야 한다. 그거 개수는 $k_1$이 켜진거 + $k_2$가 켜진거 - $k_1, k_2$가 켜진것으로 구할 수 있고, 이거까진 또 쉽게 되는거같기도? 왜냐면 둘다 켜진건 처음에 보고있으니까. $A_i$에서 $k_1, k_2, k_3$ 세개가.. 나머지들에서 세개가 다 꺼져있어야.. 근데 이건 각자 더하고 둘둘 빼고 세개 더하고.. 는 까다롭네. 앞에서 하면서 저장해왔으면 되는거같긴 한데.. 그런데, 이렇게 하다보면 결국 비트가 20개정도니까… 어? 되는거같기도 한데? 어떻게 풀 수 있나 고민해봤는데, 결국 각 비트 자체 대해서 저장한다음에, 다른 배열에서 이를 이용해서 만들어보자. $\text{cntExact}$를 해당 비트가 그대로 켜져있는것 (그 숫자 자체) $\text{cntOr}$을 켜져있는 비트중 하나라도 켜져있는것이라고 생각하면, 이걸 앞에서 얻은것들로 계산할 수 있을 것 같다. 이를 SOS DP로 알려져있다. 두 수의 and 결과가 0인 것의 개수는, $A_i$를 정했다면 ${A_i}$ 를 뒤집은 비트에서 부분집합의 합과 같다. OR은 어떻게 풀릴까? $A_i, A_j$ 모두 $K$랑 or 연산한 결과가 $K$여야 한다. 예를들어 목표가 $1101$이고, $A_i$가 $1000$이라면 $A_j$는 $?101$이어야 한다. $A_i$에서 꺼진 비트는 모두 켜져있어야 한다. 부분집합의 합을 구할때, $A$를 뒤집어서 저장하는 것으로 가능할 것 같다. $?$ 인 부분들에 대해 부분집합의 합을 계산하면 된다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<int> A(N); rep(i, 0, N) cin >> A[i]; int all1 = (1 << 20) - 1; // count and { ll ans = 0; vector<int> cnt(1<<20, 0), SOS(1<<20, 0); rep(i, 0, N) if((A[i] & K) == K){ cnt[A[i] - K]++; SOS[A[i] - K]++; } rep(i, 0, 20) rep(mask, 0, 1<<20) if(mask & (1<<i)) SOS[mask] += SOS[mask^(1<<i)]; rep(i, 0, N) if((A[i] & K) == K){ int mask = all1 - (A[i] - K); ans += SOS[mask]; } ans -= cnt[0]; cout << ans/2 << ' '; } // count or { ll ans = 0; vector<int> cnt(1<<20, 0), SOS(1<<20, 0); rep(i, 0, N) if((A[i] | K) == K){ cnt[A[i]]++; SOS[K - A[i]]++; } rep(i, 0, 20) rep(mask, 0, 1<<20) if(mask & (1<<i)) SOS[mask] += SOS[mask^(1<<i)]; rep(i, 0, N) if((A[i] | K) == K){ ans += SOS[A[i]]; } ans -= cnt[K]; cout << ans/2 << ' '; } // count xor { ll ans = 0; vector<int> cnt(1<<20, 0); rep(i, 0, N) cnt[A[i]]++; rep(i, 0, N) ans += cnt[A[i] ^ K]; if(K == 0) ans -= N; cout << ans/2; } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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"; } } 🔒 구현 코드 잠금