https://www.acmicpc.net/problem/5922
접근법
- 중간값이 X이상인 부분수열의 경우의 수
- 중간값은 홀수개인 경우 중간 위치, 짝수개인 경우 중간보다 큰 위치(celling을 해석)
- 임의의 시작 위치에서 가능한 경우의 수들을 합해나감
- 부분 수열에서 숫자의 구성을 생각해봄
- 부분수열에서 X보다 작은 숫자가 특정 개수 이상이면 조건을 만족함 ==> 수열 길이의 절반
- X보다 작은 숫자의 개수의 합, X이상인 숫자 개수의 합
- ... X보다 작은 숫자 : -1, X 이상인 숫자 : 1로 했을때 누적합
- 결국 누적합이 0보다 큰 경우이면 조건을 만족하는 부분수열일 것임
- 구간트리의 적용
- 시작위치를 변경하는 것의 처리
- 시작 위치가 바뀌면 누적합의 값도 바뀜 : 기존 값에 -1을 하거나 1을 하거나
- 누적합을 잘 변경했다고 해도, 누적합이 임의의 값보다 큰 것이 몇개인지를 알아내야함
- 구간트리 사용 : 누적합의 counting으로 구간트리 구성
- 시작위치가 바뀔때 누적합의 값을 바꾸지 않고, 기준이 되는 값을 바꿔나감
- 원래는 누적합중에서 0보다 큰 경우가 몇개인지가 궁금했지만
- 시작위치에서 1이 빠지면 = 모든 누적합에서 1을 빼줘야함 = 누적합이 1보다 큰 경우
- 시작위치에서 -1이 빠지면 = 모든 누적합에 1을 더해줘야함 = 누적합이 -1보다 큰 경우
- 시작위치가 바뀌면서 바뀐 곳 까지의 누적합 counting도 구간트리에서 제거해줌
- 시작위치를 변경하는 것의 처리
newbieski