s_i가 (면 y_i = 1, )면 y_i = -1이라고 두겠음.


이제 ( 혹은 ) 로 주어진 문자열이 주어질때 최적의 연산수를 생각해보겠음.

regular bracket sequence인지 판단하는건 잘 알려져 있는데, 1) y_i의 누적합을 보았을때 그 어떤 누적합도 0밑으로 내려가면 안됨 2) 모든 y_i의 합이 0이여야함.

그래서, 문자열이 주어질때 다음 두 변수를 생각할거임, min과 S인데, min은 y_i의 누적합중 최소값이고 S는 모든 y_i의 합임

정의에 의하여 min <= 0, min <= S인걸 알 수 있음.


1) min==0, S>=0인경우

문자열 뒤에 S개만큼 )를 붙히면 바로 끝남. 그러므로, 최적의 연산수는 S개임

2) min<0, S>=0인경우

문자열 뒤에 S개만큼 )를 붙히고, min이 0이상이 되도록 조작해줘야함. 이것은 회전연산을 통하여 뒤에있는 (를 앞으로 땡겨오면 되기 때문에, 연산수는 S-min이 됨.

3) min<0, S<0인경우

문자열 앞에 -S개만큼 (를 붙히면, min은 min-S로 변함(S가 음수임에 주의). 그런데 min<=S기 때문에, min-S<=0임. 그러므로, 회전연산으로 이 값을 0이상으로 만들어주려면 S-min개의 연산이 필요함. 그런데 이미 -S개의 연산을 했으니, 종합하면 -min개의 연산이 필요한걸 알 수 있음.


따라서 결론은:

1) S>=0인경우: S개의 연산이 추가로 필요함

2) min<0인경우: -min개의 연산이 추가로 필요함

인것을 알 수 있음. 놀랍게도 S부분과 min부분이 잘 쪼개지기 때문에, 이제 모든 부분문자열을 보면서 S와 min을 관리해줄거임.

즉,

1) 모든 부분문자열을 보며, S>=0인 모든 부분문자열에 대하여 답에 S를 더해주기

2) 모든 부분문자열을 보며, min<0인 모든 부분문자열에 대하여 답에 -min을 더해주기

를 하면 끝남. 그런데 이건 또 어떻게 하느냐? 굉장히 어려움.


일단 1)의 경우임. i를 1부터 n까지 스위핑을 한다고 가정하겠음

현재 i번째 위치를 보고 있고, s[1:i-1], s[2:i-1], ... , s[i-1,i-1]들의 S값을 다 가지고 있다고 가정하겠음.

그러면, 현재 i번째 위치를 보고 있다면, 기존에 있는 모든 S값들에 y_i를 더해주고, s[i,i]의 S값인 y_i를 또 추가해줘야함.

그리고 이렇게 저장해둔 모든 S값들의 합을 답에 추가해줌. 이렇게 스위핑을 하면 O(N)에 1)연산을 끝낼 수 있음.


문제는 2)의 경우임. i를 n부터 1까지 스위핑을 하면,

s[i+1:n], s[i+2,n], ...들의 min값을 다 가지고 있고, 1)에서 했던것처럼 이제 이 값들에 다 y_i를 더해주면 됨.

그런데, 만약 그중에 어떤 min값이 1이상이 된다면, 그 값을 0으로 만들어줘야함. 위에서 말했지만 min<=0이여야 한다는 조건이 있는걸 기억해야함.

그래서 아까 했던것처럼 그냥 스위핑 잘 하는것만으로는 안되고, 양수가 되버린 min값들을 전부 0으로 만드는 과정이 필요함.

이 과정이 굉장히 까다로운데 몇가지 후보 방법들이 있음

1) segment tree beats 2) treap같은 BST위에서 lazy propagation하기 3) 값 전부에 y_i를 더하는것을 원점을 -y_i만큼 더하는것으로 바꿔 생각하는것으로 그냥 segment tree with lazy propagation 등등

난 1), 2)밖에 생각이 안났는데 스탠딩 보니까 사람들이 잘풀어서 다른 방법이 있나 고민해봤고 3)방법이 있는걸 깨닫고 3)으로 코딩했음


아무튼 그렇게 세그먼트 트리 잘잡아서 스위핑하면 답을 구할 수 있음.

내 풀이: https://codeforces.com/contest/1750/submission/179614251


추가) 지금 생각해보니 beats 안되는듯?