상위 99.99%의 PS

들어가기 전에, 코드는 파이썬으로 작성했으니 참고했으면 좋겠다. 어자피 작동 원리는 같으니 문제는 안 된다. https://www.acmicpc.net/problem/16911 16911번: 그래프와 쿼리 첫째 줄에 정점의 개수 N(2 ≤ N ≤ 100,000)과 쿼리의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제를 풀어보자. 처음에는 어떤 두 정점도 연결되지 않은 상태이고, 다음 쿼리들을 수행하는 문제이다. 1번 쿼리: 두 정점을 연결하는 간선을 추가한다. 2번 쿼리: 두 정점을 연결하는 간선을 제거한다. 3번 쿼리: 정점 u에서 v로 가는 경로의 존재 여부를 출력한다. 2번 쿼리가 없다면, 단순하게..

https://www.acmicpc.net/problem/17474 17474번: 수열과 쿼리 26 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = min(Ai, X) 를 적용한다. 2 L R: max(AL, AL+1, ..., AR)을 출력한다. 3 www.acmicpc.net [알고리즘 분류] Segment tree beats greedev에게 세그비츠가 웰논인지 물어봤는데, 다음과 같은 답변을 받았다. (수쿼 25~30은 모두 세그비츠를 사용한다고 한다.) 나는 정말 무식하지만, 최대한 열심히 설명해보도록 하겠다. 나보다 설명을 몇십배는 잘 해둔 글이 수두룩하기 때문에, 나의 글로..

https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net [알고리즘 분류] Segment Tree (with lazy propagation) Euler Tour Technique 오일러 경로 테크닉이라는걸 배우고, 기초문제를 풀어보았다. 오일러 경로 테크닉은 루트가 있는 트리에서 어떤 정점의 서브트리에 속하는 정점들을 연속된 수로 renumbering할 수 있는 기술이다. 일단 나는 이렇게 이해했고, 이 문제는..

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..