79brue의 PS 블로그

뭔가 백준 솔브 수가 높거나 주변 사람들이 많이 얘기를 하는데 나는 뭔지 잘 모르겠는 문제들이 많았고, 이런 문제들을 좀 모아서 풀어 보기로 했다. 첫 번째 문제는 유명한 세그비츠 문제인 수열과 쿼리 25로 정했다. 세그비츠 문제를 아예 안 풀어 본 건 아닌데, 이 문제는 안 풀어봤었고, 뭔가 나만 모르는 웰노운 같아서 풀어봤다. 링크접근이런 특이한 형태의 세그먼트 트리를 쓰는 문제는 일반적으로 적당한 퍼텐셜 함수를 만들어서 푸는 경우가 많다. 가장 대표적인 예시가 수열과 쿼리 26인데, 이 경우 min 연산이나 max 연산을 할 때 서로 다른 수의 개수가 줄어드는 경우가 많다는 사실을 이용해 퍼텐셜 함수를 정의한다. 이 문제도 비슷한 생각을 할 수 있다. 비트 연산의 성질상,and 1이나 or 0은 원..