블로그 옮겼습니다

우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..

http://codeforces.com/contest/803/problem/D 너무 간단한 파라메트릭서치문제이다. 보자마자 파라메트릭서치임을 알았는데 구현이 막혀서 1시간동안 풀이못했기에반성하는 마음으로 기록용으로 글을 올린다..(정확히는 파라메트릭서치가 아니라 바이너리 서치라는데 나는 파라메트릭서치가 편하다..) 공백, 하이픈(-), 알파벳 대소문자로 이루어진 문자열 한줄과 만들 수 있는 최대 줄 수 K를 입력받는다.공백과 하이픈에서 줄을 바꿀 수가 있을 때 K줄을 넘지 않도록 하는 최대 가로폭(width) 를 구하는 문제이다.가로폭은 각 줄의 길이중 최대인 길이를 말한다. 그럼 그냥 단순히 가로폭의 상한을 정해놓고 그 가로폭을 최대로 갖도록 최대한 한줄에 꾸겨넣을 때 줄의 수를K개 이하로 만들 수 있..