벨에삐

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 구간에 대한 쿼리를 처리하는 문제입니다. 전형적인 인덱스 트리, 세그먼트 트리 문제입니다. 모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다. #include #define ll long long using namespace std; const int SIZETR = 262144;..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net https://belepi.tistory.com/8 에서 다룬 백준 10868번: 최솟값을 풀어봤을 경우 쉽게 접근할 수 있는 문제입니다. 모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다. #include #define SIZETR (262144) // 2^18 using..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 주어진 문제의 크기를 보고 알맞은 시간 복잡도의 자료구조와 알고리즘을 선택하고 설계하는 것이 중요합니다. 기껏 프로그램을 구현했는데, 시간초과로 인해 처음부터 다시 풀어야 하는 상황은 피해야 합니다. naive한 풀이로는 아래 코드처럼 매 query마다 a번째 정수부터 b번째 정수를 탐색하면서 최솟값을 찾아 출력하는 O(MN)의 풀이를 생각해볼 수 있습니다. 다..