AtCoder Beginner Contest 253 F - Operations on a Matrix

F - Operations on a Matrix

세그먼트 트리 하나로 쿼리들을 관리하고, 질의가 들어왔을 때 과거의 세그먼트 트리가 필요한 것 까지는 알았다.

하지만 과거에 세그먼트 트리를 전부 저장하면 되지 않을까 생각했는데, 쿼리가 20만 개라 말도 안 되는 것이다.

계속 어떻게 해야 과거의 세그먼트를 꺼내서 답을 구할 수 있을까 생각했는데 답은 간단했다.

쿼리가 들어올 때 전부 쿼리 순서대로 쿼리를 저장한다.

그리고 과거의 세그먼트가 필요하다면 필요한 과거의 세그먼트와 필요한 답을 적어 놓은 다음에

다시 그 쿼리들을 시뮬레이션을 한다. 그렇게 되면 미래에 필요한 세그먼트들을 이미 알고 있기 때문에

미래에 필요한 세그먼트가 나타나면 미래에 필요한 답을 미리 저장해 놓는 방식으로 하면 된다.

결론 : 오프라인 쿼리를 잘 이용하자.