joseph0528 코딩 블로그

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

문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다. K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지..

문제 설명이 이게 다인 문제 설명은 간단한 문제이다. 이 문제를 처음 볼 때 이상한 수학으로 풀어야 되는 건가 싶을 수 있지만 사실 세그를 사용해서 풀 수 있다. 일단 |p [i]-p [j]| 를 1번이라고 하고 |q [i]-q [j]| 를 2번이라고 하겠다. 이 문제는 1번과 2번 중 작은 값을 골라야 하기 때문에 1번이 작은 경우와 2번이 작은 경우 이렇게 2개로 나눌 수 있다. 1번이 작거나 같은 경우부터 생각해보자. 1번이 작거나 같을려면 (j = p[j] 일때 p[i] < p[j] 일때 p[i]-p[j]

https://www.acmicpc.net/problem/17163 17163번: 가희의 수열놀이 (Large) 첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 106, 1 ≤ mod ≤ 2×109) 이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어 www.acmicpc.net 문제에 쿼리가 있어 세그라는 생각을 할 수 있지만 1

https://www.acmicpc.net/problem/17668 17668번: 시험 $N$명의 학생이 수학 부문과 정보 부문이 있는 시험을 쳤다. $i$번째 ($1 \le i \le N$) 학생은 수학에서는 $S_i$점을, 정보에서는 $T_i$점을 받았다. T교수와 I교수는 각 학생이 시험을 통과할지 말지를, www.acmicpc.net 이 문제 세그 스위핑이라는 방법이 있다고는 하지만 그 방법이 아닌 2차원 머지 소트 트리를 박는 방법으로 했다. 방법은 생각보다 간단한다. A에서 이분 탐색을 해 입력값 이상인 값들의 위치에 있는 B에서 이분 탐색을 또 하고 거기서도 이상인 값들의 위치 중 합이 입력값 이상인 값을 찾아주면 된다. 말만 간단한거 같지만 이 방법을 그대로 머지 소트 트리에 해주면 된다...

https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만 간단한 세그로 풀수 있다. 일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자 2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다 마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데 1번 쿼리에서 b번째 사탕..

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 티어 : 골드 1 www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 문제를 보면 바로 구간 곱이라는 것을 알 수 있다 하지만 구간 곱을 구현한 뒤 제출하면 시간 초과를 받는다. 이유는 값이 너무 커져서 그런것인데 어차피 값을 원하는 게 아니라 부호만 알면 되는 거기 때문에 음수일 경우 -1을 곱하고 양수일 경우 1, 0일 경우 0을 곱해주면 된다. 출력에서도 구간 곱이 양수면 +, 음수면 -,0이면 0을 출력해주면 된다. #include ..

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