CF 1715C

https://codeforces.com/contest/1715/problem/C

Problem - C - Codeforces

머리가 안돌아가서 그냥 관찰로 대충 찍어맞췄는데 그마저도 푸는데 거의 1시간 걸림.

 

전체 g 구하는 방법:

1, 1, 2, 2, 2, 3, 3 이 있으면

[1, 1] + [2, 2, 2] + [3, 3] 이렇게 같은 수들 묶음 사이에 +가 있다 생각하고

각 +마다 +를 포함하는 구간의 개수를 세면 된다.

거기에 nC2를 더하면 된다.

왜 이게 되냐면 배열의 모든 원소가 같을 경우에 g의 합이 nC2다.(모든 구간에서 g가 1이므로)

그리고 어떤 구간이 +를 하나 포함할 때마다 그 구간에 해당하는 g는 1씩 증가하기 때문이다.

 

이제 쿼리가 들어올 때 마다 i 양 옆에서 +의 변화에 따라 잘 처리해 주면 된다.