6. 3

• <GSS7>을 어떻게 깔끔하게 풀까 고민하면서 오전을 보내고.. HLD를 구현하는 도중 spoj가 터져서 그냥 딴거나 해봐야지 하고 MO's Algorithm 코딩을 해봤다. 이 튜토리얼을 따라서.. 첫번째 실험대상은 <Powerful Army>로! sum query가 각 숫자의 occurrence에 달려있는 괴랄한 식인데, marginal하게는 쉽게 구할 수 있으므로 MO's algorithm에 적당했다. 5초 제한시간에 4초로 AC를 받았는데 조금만 쿼리 순서를 바꾸자 TLE가 뜬다..ㄷㄷ #
• <GSS7>을 풀었다!!! HLD도 이제 조금은 익숙해진 느낌? merge의 순서가 정말 중요해서 WA를 좀 맞았다.-,- # <NAVI>의 원조 <QTREE>도 풀었다. #
• <INCSEQ>를 풀었고 #, <INCDSEQ>도 풀었당. # 원리는 같음! \(dp[i][k]=\sum dp[j][k-1] \text{ where } S_i<S_j, i<j\)를 구간합으로 구해낼 수 있구나~
• segment tree만 너무 풀어서 지겨워서 CF #304 Div2를 virtual participation했다. 5분후 시작~ : A,B,C,D까진 정말 단순하게 풀렸으나 E를 못풀었다ㅠㅠ flow문제를 풀어본지 오래되서 못알아봤음.. 전반적으로 쉬운 contest였던듯..