[Hard] FoxSearchingRuins

O(n*LR*n) DP 는 쉽게 생각할 수 있다. D[i][k] = i번 보석의 위치까지 좌우이동을 k번 했을 때 얻을 수 있는 최대 가치 하지만 빼박 TLE 다. 이걸 seg tree || fw tree 를 이용해 O(n*LR*logW) 로 내릴 수 있다. 현재 y번 행을 보고 있다하면 0번~y-1번 행에 있는 보석들 중에선 각 열마다 가장 아래에 위치한 보석들만 고려해도 된다. 그 위에 보석이 있었다고 해도 바로 밑으로 죽 내려오기만 하면 되기 때문이다. 그래서 각 열마다 가장 아래에 있는 보석에 도달했을 때의 dp값을 max tree 에 때려넣고 y번 행의 dp값을 구할 때 그 max tree 를 참조하면 된다는 아이디어다. 실제 구현은 좀 더 까다롭다. 현재 보고 있는 보석의 x좌표를 x, 좌우이동을 k번 했다 하면 참조해야하는 값은 (x-1,k), (x-2,k), ... 가 아니라 (x-1, k-1), (x-2, k-2), ..., (x+1, k-1), (x+2, k-2), ... 이기 때문이다. 보석의 왼쪽은 x-k 가 같다는 점, 오른쪽은 x+k 가 같다는 점을 이용해 그 값을 tree의 id로 두면 된다. 그래서 max tree 가 총 2*(W+LR+1) 개 필요하다. 여기서 다음과 같은 관찰이 필요한데 한 행 안에서 보석들을 먹을 땐 무조건 한방향으로 진행하면서 먹어도 된다. 즉, 보석을 먹을 때는 방향전환을 하지 않는다. 물론 방향전환이 필요할 때도 있는데, 이건 다음 행으로 내려가기 위한 예비동작이라고 생각하면 된다. 그래서 행을 처리할 때는 위의 관찰을 이용해 왼쪽->오른쪽 으로 가면서 최대값을 구한 배열, 오른쪽->왼쪽 으로 가면서 최대값을 구한 배열 2개를 만들고 마지막으로 두 배열 중 최대값을 max tree 를 갱신하는것과 답을 구하는것에 사용하면 된다.