Doby's Lab

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 한 문제만 풀면 플레티넘이라서 멋지게 피날레를 장식하고 싶은 마음에 풀 수 있을 거 같은 다이아 문제를 골랐었다. (그러지 말 걸 그냥 플레 문제 2개 더 풀걸) 다이아다 보니 당연히 어려웠고, 아 이게 다이아인가 싶었다. 우선 쿼리의 종류는 4가지다. x y v: Ai = (Ai + v) % MOD를..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 직전의 포스팅과 똑같은 문제다. https://draw-code-boy.tistory.com/203 [알고리즘] 백준 1725번: 히스토그램 (C++), 세그먼트 트리의 응용 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 이번 문제는 유난히 어려웠다. 처음에 떠올랐던 방법은 히스토그램의 높이 중 제일 작은 것을 골라서 전체 구간의 길이와 곱해준 값을 출력해줬었다. >> 차라리 이럴 거면 입력받을 때 최솟값을 구해서 구간과 곱해주는 건데 세그먼트 트리 문제라는 이유로 세그먼트 트리를 구한 게 멍청했다. 하지만, 이 방법이 안 되는 이유는 두 가지에서 떠올랐다. 어떤 높이가 0인 경우 >>..

https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net N번 부대에 필요한 사람 수만큼 사람을 1번부터 차례대로 집어넣는다. 어떠한 X번 군번이 주어졌을 때 이 사람은 어느 부대를 들어가야 하는지 알아내야 하는 문제다. 1번 부대부터 필요한 사람 수들을 더하면서 만족하는 범위 안에 들어가면 답을 도출할 수 있다. 하지만, 쿼리는 M개 부대의 수는 N개로 O(N * M) >> O(N * M), 500,000 * 10,000이 되어 시간 초..

https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 이번 문제는 문제에서 "가장 강렬한 빛의 광고판만이 눈에 들어온다."라는 말에서 구간 최댓값 세그 트리를 짜주면 되는 문제였다. 다만 어떤 구간인지에 관해서는 "슬라이딩 윈도우"라는 알고리즘(?)이 튀어나왔었다. 잠깐 구글링 해봤는데 알고리즘이라 하긴 그렇고, 테크닉(?) 같은 느낌이다. 따로 설명은 하지 않겠다. (나중에 어려움을 겪으면 그때 정리하겠다.) 시야 M이 주어..

https://www.acmicpc.net/problem/18436 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net 이번 문제에서 포인트는 3가지라고 생각한다. (그냥 2가지 + 개인적인 1가지) 홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다. 홀수 세그 트리로 만드는 게 더 편하다. update를 전처리 함수를 차용해서 만들었다. [홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다.] 처음엔 둘 다 만들어야 하나 생각했지만 하나..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 구간합 lazy propagation으로 구현해주었다. >> 1번 쿼리 (구간 합 업데이트) 때문에 세그먼트 트리를 써야 했다. 그런데 구간 업데이트라서 lazy propagation이 필요했다. lazy propagation 개념 공부할 때와 똑같은 구성이라 그런지 어렵게 느껴지진 않았었다. #include #define MAX (100000 + 1) #define ll lo..

https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 업데이트를 하는 부분에서 문제가 있었는데 leaf 노드에서 value값을 새롭게 할당하고, (start 즉, leaf노드만 새로운 값으로 할당 시키고 나머지는 update를 시켜주면 된다. int update(int start, int end, int node, int index, int value) { if (ind..