우선 prefix sum으로 a[x]−a[x−1]+a[x−2]−…a[1]a[x]−a[x−1]+a[x−2]−…a[1]을 각 xx에 대해 구합니다. 이 prefix sum이 일치하는 쌍의 갯수를 구하면 답에 근접합니다.
답이 아닌 이유는 구간 [l,r][l,r]이 답이 되려면 중간 a[l]a[l], a[l+1]−a[l]a[l+1]−a[l], a[l+2]−a[l+1]+a[l]…a[l+2]−a[l+1]+a[l]…이 모두 0 이상이여야 하는 추가적인 조건을 만족해야 하기 때문입니다. (돌을 항상 0개 이상 가져가야 하므로)
이거를 투 포인터, 레이지 세그멘트 트리 등의 방법으로 좀 관리할 수 없을까 하고 생각했는데 효율적인 방법이 떠오르지 않았습니다.
힌트좀
홀짝성에 따라서 a_l 앞에 붙는 부호가 달라지기때문에 세그먼트 트리를 홀짝성을 기준으로 나눠서 잘 관리하면 됨. 즉, 첫번째 segtree는 1,3,5,7,..번째를 관리하고, 두번째 segtree는 2,4,6,...번째를 관리하면 됨
나도 그 생각 했었는데 그러면 홀로 시작하고 짝으로 끝나는 sequnce도 세줄수 있나요 암튼 ㄳㄳ
b_i = a_i - a_i-1 + a_i-2 ... 이런수라고 두면, [l,r]이라는 구간에 대해서 l과 r-1의 홀짝성이 같으면 b_r - b_l-1, 다르면 b_r + b_l-1 사용하면 됨. 홀짝에 대해서 서로 다르게 탐색해야함
나도 존나 궁금해 레이지 세그트리인가 부분합인가 막 고민하다가 탈주함
그거 montone queue techinque 을 사용하면 O(N)에 처리가 가능해짐. 홀수 번째에서는 현재 prefix 보다 큰 이전 prefix 제거하고 짝수 번째에서는 현재 prefix보다 작은 이전 prefix 제거하면됨