https://www.acmicpc.net/problem/17407
접근법
- 올바른 괄호 문자열의 조건
- () 쌍이 맞고
- 어느 한 부분에서도 )가 초과되지 않아야함
- ( = 1, ) = -1로 바꿔서 생각해보면
- 1 ~ n까지 sum = 0이고
- 1 ~ n까지 누적합의 최소값이 0이상이어야함
- 누적합을 담는 최소값 구간트리 사용
- ( -> )로 변경되면
- sum = sum - 2가 됨 (1이었던 것이 -1이 되므로)
- 변경된 위치 이후의 누적합들은 모두 -2가 됨 ==> lazy propagation
newbieski