[CF 1042D] Petya and Array - 1800 문제 설명 : 배열 a[1], a[2].. a[n]이 주어져 있다. 여기서 임의의 [l, r] pair를 골랐을 때 $a[l]+a[l+1]+...a[r] < t$ 을 만족하는 pair가 총 몇 쌍인지 세야한다. 문제 풀이 : $a[l]+a[l+1]+..a[r] < t$ 식을 [1,n]까지의 누적합을 저장하는 누적합배열 $psum[]$ 배열을 활용하여 $psum[r] - psum[l-1] < t$ 로 변형할 수 있다. 그럼 결국에는 $psum[r] - t < psum[l-1]$을 구하는 문제랑 똑같아진다. 변수가 l, r 총 2개이기 때문에 l 이나 r 을 고정시켜놓고 나머지 다른 값만 log만에 구하면 된다. 나는 r을 고정시켜놓고 이를 만족시..
[BOJ 7469] K번째 수 - P3 문제 설명 : 문제 풀이 : mergesort tree를 이용해서 풀 수 있다. megesort tree는 트리의 노드가 값 하나가 아니라, 원소 그 자체를 담고 있기 때문에 여러개의 원소를 담고 있을 수 있다. 마치 merge sort가 되는 과정을 tree화 시킨 것이라고 보면 된다. 그래서 이분탐색으로 mid값을 지정하여 [l,r]구간에 mid 이하의 값이 몇 개인지를 log 만에 찾을 수 있다. 배울 점 : mergesort Tree를 이용하면 N개의 원소 중에서 [l,r]구간의 x보다 크거나 작은 원소의 개수를 log만에 구할 수 있다. #include #include #include using namespace std; const int SIZE = 10..
[BOJ 1725] 히스토그램 - P5 문제 요약 히스토그램에서 만들 수 있는 직사각형 중에서 가장 큰 넓이를 찾는 문제이다. 문제 풀이 직사각형의 넓이는 (r - l + 1) * getMin(l,r) 로 구할 수 있다. 여기서 문제는 N = 10만이므로 l,r을 전탐색으로 돌리면 시간이 초과하게 된다. 해결 방법은 세그먼트 트리에 가장 작은 값의 인덱스를 저장해놓는 것이다. 그래서 퀵소트가 작동하는 방식처럼 매 [l,r]구간에서 가장 작은 값의 인덱스를 찾아서 넓이를 구한 다음, 그 인덱스를 기준으로 좌, 우를 갈라서 똑같이 재귀적으로 넓이를 구해주면 된다. #include using namespace std; typedef long long ll; const int SIZE = 100009; cons..