joseph0528 코딩 블로그

이 문제는 설명자체는 간단한데, 트리가 주어지고 1번 쿼리는 트리의 노드를 바꾸는 거고, 2번 쿼리는 현재 만들어진 트리에서 1번 노드에서 v 노드로 가는 길에 1번 노드와 가장 가까운 검정 노드의 번호를 출력하는 문제이다. 이 문제도 여러 가지 풀이 방법이 있는 걸로 알고 있고 가장 대표적인 풀이가 HLD(Heavy heavy Light Decomposition)으로 알고 있는데, 그 풀이가 아닌 ETT(오일러 투어 테크닉) 와 lazy 세그 (느리게 갱신되는 세그먼트 트리), sparse table(희소 배열)을 이용한 풀이를 작성하겠다. 이 문제의 핵심은 2번 쿼리니 1번 쿼리는 2번쿼리의 구조 내에서 구현해 줘야 된다. 그러므로 2번 쿼리부터 설명하겠다. 1부터 v 로 가는 길에서 1에 가장 가까..

https://www.acmicpc.net/problem/6164 6164번: Hotel The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacatio www.acmicpc.net 이문제는 일자로 나열된 방들이 있고 1번 쿼리는 소들은 n개가 연속되게 비어있는 방을 쓸려고 하는데 이때 그런 방이 있다면 연속된 n개..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18437 18437번: 회사 문화 5 총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직적인 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. www.acmicpc.net 컴퓨터가 켜져 있는 상태를 1, 컴퓨터가 꺼져있는 상태를 0으로 두고 구간을 1 또는 0으로 변경한 뒤 구간 합을 출력하면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu[N]; ll cnf=0..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..

solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/14287 14287번: 회사 문화 3 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 다른 회사 문화 문제와는 다르게 위에서 아래로 값을 더해주는 것이 아닌 밑에서 위로 값을 더해주는 문제이다. 이 문제의 풀이는 생각보다 간단하다. dfs으로 새로 해당 구간을 만들고 그 구간에 대한 이진트리를 그리고 x노드의 값에 w를 더한다고 해보자. 그러면 x를 가지고 있는 구간에만 변경이 생긴다. 그러므로 구간이 (x,x)인 위치에 w를 더해주면 x를 포..

solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 회사 문화 1과 같은 문제인데 1은 마지막에 모든 정점마다 합을 구해주는 거고 2는 2가 들어올 때마다 구간의 합을 구해주는 것이다. BOJ 14267(회사 문화 1)풀이 solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net dfs으로 각 위치마다 구간을 새로 저장해준 뒤 입력으로 들어오는 값의 구간에다가 w를 더해주고 마지막에 1부터 n까지 i번째점의 구간 합을 출력해주면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18407 18407번: 가로 블록 쌓기 가로 블록만 등장하는 테트리스 게임을 해보려고 한다. 가로 블록은 총 N개가 등장할 예정이고, 등장하는 순서대로 1, 2, ..., N번이다. i번 블록의 높이는 1이고, 너비는 Wi이다. i번 블록은 왼쪽 벽 www.acmicpc.net 새로 떨어지는 블록은 자신의 구간에서의 최댓값+1이다. 그러므로 세그레이지로 max를 구해주고 max+1 값을 구간에 저장해준다. 그리고 max값이 최대 높이일 경우 최대 높이를 올려준다음 마지막에 나온 최대 높이를 출력해주면 된다. #include using namespace std; typedef long long ll; struct qu{ ll ..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net 이문제는 트리에 어떤 노드가 선택되었을 때 그 노드와 노드의 자식들에게 w만큼 값이 더해지는 문제다 대신 이 문제는 다른 평범한 세그먼트 트리처럼 이진트리가 아니다. 그럼 어떻게 할 수 있을까? 예시에 있는 입력을 가지고 트리를 만들면 이렇게 된다.(좀 이상한 건 어쩔 수 없다) A부터 E까지 순서대로 1,2,3,4,5라고 할 때 A..

solved.ac 티어 : 다이아 4 www.acmicpc.net/problem/16910 16910번: mex와 쿼리 mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다. 비어있는 배열 A와 쿼리 N개가 주어졌을 때, www.acmicpc.net 생각보다 간단한 세그레이지이다. 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다. 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다. 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서,..