5월 26일#세그먼트 트리 재활

세그 트리 문제를 다시 풀고 있다. 구현에 초점을 맞췄음.

2021.01.23 - [Problem Solving] - 머리로만 문제 풀기 글에 있는 문제들 중 세그 카테고리 문제들을 구현해봤다.

9623 부분 수열의 길이

처음에는 플4라는 게 믿기지 않았던 문제.
업데이트가 없기 때문에 누적합 배열로 구간의 합을 나타낼 수 있는 것이 핵심.

기본적으로 스위핑인 것은 잘 보인다.
끝점 i를 고정시키고 시작점 j+1중 가장 뒤에 있는 것을 찾는 느낌
$0<=j<i$, $sum[i]-sum[j]>=X$가 만족되어야 한다.

결국 $sum[j] <= sum[i] - X$인 최대 j를 찾는 문제가 되고,
이는 스위핑 + 어떤 방법으로 해결할 수 있다.

이제 나는 처음에 이 방법을 1. sum[i] 좌표 압축 + 2. sum[i]-X 이분탐색 + 3. sum[i] 구간에 있는 최대 인덱스 저장 세그 트리로 정했는데... 뇌절인게 판명 났다.

이제 sum[j] <= sum[i]-X인 j가 존재한다면, 그냥 그때 그때 조건이 만족되는 순간 보는게 이득이다.
i가 커지면 커질 수록 i-j도 커지기 때문에 답이 될 확률은 없다.
따라서 pq로 sum[j]가 작은 순서로 관리하면서 sum[i]-X보다 sum[j]가 작은 경우 i-j로 답 갱신을 시도해주면 된다.

5419 북서풍

점들 y좌표 좌표압축 후 (x좌표 작은,y좌표 큰) 순서 정렬. 자기 y좌표 이상 있는 애들 개수 세주기.
세그 기본 문제.

9034 순위

오프라인 쿼리 + 좌표압축 + 세그/펜윅이 정풀이지만 Indexed_Set 쓰자.
Indexed Set 매우 느리다 ㅡ.ㅡ
애초에 입력량이 매우 많아서 (테스트 케이스 20개 * N <= 10^6) 펜윅을 써야만 하는 문제였음

20052 괄호문자열?

여는 괄호를 1, 닫는 괄호를 -1로 모델링 한다음

[a,b] 구간에 대해서 올바른 괄호문자열일 조건은
sum[b] - sum[a-1] == 0 이고 
구간에 속한 모든 i에 대해 sum[i] - sum[a-1] > = 0 임을 이용한다.