2021년 1월 24일 PS일지

1. 하루 3솔

레이지 세그먼트 트리 형제
1. 수열과 쿼리 23 ✔
2. 버거운 버거 ✔ - 레이지 세그 3개를 한 문제에 동시에 박은 건 처음이다.
확실히 구현량이 많아질 수록 실수가 잦다. 빨리 찾아서 다행이지만 더 치밀해지자.
끝나고 다른 풀이를 보니 훨씬 간단하던데 배우자.
내 풀이는 여는 괄호를 1, 닫는 괄호를 -1로 모델링 하고 min(sum[i]) >= 0 && sum[n] == 0 이 만족되어야 올바른 괄호 문자열이다를 이용하는 풀이다.  min(sum[i]) 이 조건이 괄호를 반전하면 max(sum[i])를 구하는 것이기 때문에
(1) 구간 곱, 합을 업뎃을 지원하는 최솟값/최댓값 쿼리 세그먼트 트리와
(2) 구간 곱 업뎃을 지원하는 구간합 쿼리 세그먼트 트리가 필요하다.
구현 꽤 빡셌다. 템플릿 덕분에 노동은 많이 줄었지만 역시 많은 시간을 투자했다.

주때님 풀이는 ... 하 ㅋㅋㅋ 괄호 문자열을 이용한 문제를 풀 때 꼭 익혀야할 기술을 사용한다.
바로 -> 노드 별로 '짝이 안 맞는 여는/닫는 괄호의 수' 저장하기.
두 노드를 합치는 연산이 매우 간단해진다. 이 문제의 경우 괄호를 반전시켰을 때 쌍 안 맞는 여는/닫는 괄호의 수를 swap해주면 되므로 lazy propagation이 가능하다.
이 스킬을 1월 7일에 이 문제를 풀면서 익혔었던 기억이 난다.2번이나 연속해서 나온 것 보면 꼭 익혀야 하는 풀이다. 외우자.
+ sebinkim님은 아예 레이지도 안 쓰셨다 ㅋㅋㅋㅋㅋ 코드 bb
언젠가 갓이 될거다.
3. mex와 쿼리✔ - 역시 레이지 세그를 쓰는 오프라인 쿼리 문제
레이지 이해하는데 도움이 됐다.