상위 99.99%의 PS

https://www.acmicpc.net/problem/13512 13512번: 트리와 쿼리 3 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net Heavy-Light Decomposition 일단 트쿼 3을 풀기 전에, LCA 2를 HLD를 이용해서 풀어보자. 1. dfs를 통하여 한 노드를 루트로 하는 서브트리의 크기를 저장해둔다. 1 2 3 4 5 6 7 def dfs(x, p): par[x] = p sz[x] = 1 for i in g[x]: if i != p: sz[i] += dfs(i, x) return sz[x] cs..

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net Lazy Propagation in Segment Tree 1번 쿼리는 (ax + b) * 1 + v = ax + b + v 2번 쿼리는 (ax + b) * v + 0= (v * a)x + v * b 3번 쿼리는 (ax + b) * 0 + v = v 꼴로 갱신할 수 있다. 곱하는 값, 더하는 값에 대해..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation 기초 문제이다. 모른다면 읽고 오자. https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220824350353 기존 세그먼트 트리의 방식으로라면 갱신 하나에 O(NlgN)이라는 시간이 걸려 총 O(MNlgN)이라..

https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i

https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 정렬된 배열 \(A\)가 있다고 하자. 이 \(A\) 내에서 어떤 수 \(k\)보다 큰 수의 개수를 \(O(N)\)보다 빠른 시간에 구하려면, 이진 탐색을 사용하여 \(O(lgN)\)에 구할 수 있다. 그런데 이 문제는 배열이 정렬되어 있지 않고, 그리고 구간을 나누어 쿼리에 답하라고 한다. 만약, 배열을 잘 잘라서 정렬된 상태로 가지고 있으면, 그 잘려진 배열 ..

www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 세그트리 기초문제이다. 최댓값 세그트리를 만들어두고, 시야 범위 내에서 최댓값을 찾는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 seg = [0 for _ in range(4040404)] def init(n,s,e): if s == e: seg[n] = a[s-1] return seg[n] mid = (..

www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그트리 기초문제?이다. 1~K번째 부대 인원의 수의 총합을 A_k라고 할때, x번 군인의 위치는 \(A_{k-1} \lt x \le A_k\) 를 만족하는 가장 작은 k가 되고, 이는 이분 탐색으로 빠르게 구할 수 있다. -소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..