넘치게 채우기

https://www.acmicpc.net/problem/10868BOJ - 최솟값문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 1초메모리 제한: 256MB 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 입력첫째 줄에 N, M이 ..

https://www.acmicpc.net/problem/16975BOJ - 수열과 쿼리 21문제 유형: 세그먼트 트리(with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 512MB 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다.2 x: Ax 를 출력한다. 입력첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 쿼리가 한 줄..

https://www.acmicpc.net/problem/10999BOJ - 구간 합 구하기 2문제 유형: 세그먼트 트리 (with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤..

https://www.acmicpc.net/problem/11505BOJ - 구간 곱 구하기문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 1초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. ..

https://www.acmicpc.net/problem/2357BOJ - 최솟값과 최댓값문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 2초메모리 제한: 192MB 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을..

https://www.acmicpc.net/problem/6549BOJ - 히스토그램에서 가장 큰 직사각형문제 유형: 히스토그램, 스택(모노토닉 스택), 세그먼트 트리, 분할 정복, 투 포인터문제 난이도: Platinum V시간 제한: 1초메모리 제한: 256MB 문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 ..

https://www.acmicpc.net/problem/2042BOJ - 구간 합 구하기문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 ..