[BOJ 2243] 사탕상자 - P5 문제 설명 1부터 100000까지 라벨이 붙은 사탕이 있다(초기에는 아무 사탕도 없는 상태). 두 가지 쿼리가 들어오는데 첫 번째 쿼리는 k번째로 작은 라벨이 몇 번인지 찾는 것(출력)이고 두 번째 쿼리는 'k번'사탕을 m개 추가하는 것이다. 풀이 [1,1000000]숫자 그대로를 세그먼트 트리의 인덱스로 사용할 것이다. k번째로 작은 라벨이 몇 번인지 찾기 위해서 트리의 i번째 노드는 i번 사탕이 총 몇 개 있는지를 저장하고 있다. 그래서 root 노드에는 결국 전체 사탕의 개수가 담기게 된다. 이제 쿼리에서 루트->리프로 내려갈 때 left child로 내려가면 [1,tree[left]만큼 작은 수가 저장되어 있다는 뜻이다. 따라서 k가 tree[left]보다 크..
[BOJ 1517] 버블 소트 - P5 문제 설명 : n개의 수를 버블 소트할 때, swap이 총 몇 번 일어나는지 세야 한다. 문제 풀이 : i번 째 수를 기준으로 자신의 왼쪽 ( [1, i-1] ) 에 있는 수들 중에서 자신보다 큰 값이 몇 개인지 세면 된다. n이 50만이기 때문에 log 시간만에 세야 한다. 두 가지 풀이가 가능하다. 첫 번째 풀이는 mergesort tree를 이용하면 된다. mergesort tree는 [l,r]구간 상에서 x보다 작은 수의 값을 log만에 구할 수 있다. 이는 얼마 전의 k번째 수 문제에서도 언급했었다. 두 번째 풀이는 바로 offline query를 이용하는 것이다. 이 문제는 쿼리별로 독립시행이다. 즉 이번 쿼리의 정답이 그 이후의 쿼리의 정답에 영향을 끼..
[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..
[CF 1512E] Permutation by Sum - 1600 문제 요약 : 1~n수 중에서 (r-l+1)개 중복없이 뽑아서 s만들 수 있는지를 묻고 있다. 문제 풀이 : n부터 1씩 줄여나가면서 누적합을 쌓아가면서 s를 만든다. 이때 만들어진 수의 집합은 최소의 개수이므로 (r-l+1)개보다 적거나 같을 것이다. 만약 크다면 s를 만들 수 없다는 뜻이다. 개수를 늘리기 위해서는 작은 값부터 2개로 쪼개면 된다. 예를 들어 x라는 값을 쪼갠다면 (1,x-1) 또는 (2,x-2) 또는 (3,x-3)...이런 식이다. 이때 쪼개진 결과로 나오는 두 개의 값은 초기 집합과 겹치면 안된다. 겹치지 않는 것이 확인이 된다면 set에서 두 값을 insert 해주고 원래 x값은 삭제해준다. 가장 작은 값부터 쪼개..
[CF 1333C] Eugene and an array - 1700 문제 설명 : 배열 a의 subarray 중에서, 모든 원소의 합이 0이 아닌 경우의 개수를 구하여라. 풀이 : subarray의 합이 0이 된다는 말은 바꿔 얘기하면, prefix sum배열을 만들었을 때 값이 같은 원소가 두개 이상 존재한다는 뜻이다(그 두 지점을 각각 a,b라고 했을 때 pref[b] - pref[a-1] == 0이 될 것이므로). 따라서 왼쪽->오른쪽으로 pref배열을 돌면서 나오는 값을 map에다 집어 넣는다. key값은 누적합 값 자체를 넣을 것이고 value에는 그 값이 가장 최근에 몇 번째 인덱스에 등장했느냐를 저장한다(정확히는 등장한 인덱스 +1의 위치). 그러면 현재 prefix sum과 일치한 값이 나..