Animal Observation (hard version)
Contest: Codeforces Round 620 (Div. 2)
Difficulty rating: 2400
Tags: data structures, dp, greedy

The only difference between easy and hard versions is the constraint on $$$k$$$.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:

- On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days.
- On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days.
- If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day.

Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.

Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le m$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

Output format:
Print one integer – the maximum number of animals that can be observed.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The optimal way to observe animals in the four examples are as follows:

Example 1:

Example 2:

Example 3:

Example 4:

Example input:
4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4

Example output:
25

Example input:
3 3 1
1 2 3
4 5 6
7 8 9

Example output:
31

Editorial:
We can further advance the idea we used in F1 to reduce the time complexity.
Solution: $$$O(nm\log{m})$$$
Let's generalize all three cases we discussed in F1. Let's make a lazy segment tree supporting range addition update and range maximum query. Each node represents the maximum value of ($$$DP[i-1]$$$ minus the sum of the animals appearing on the $$$i$$$-th day in the intersected area) in the corresponding interval. Then we can add $$$sum(animal[i \ldots i+1][j \ldots j+k-1])$$$ to the maximum value of the segment tree to determine $$$DP[i][j]$$$.
For the $$$i$$$-th day, we insert $$$DP[i-1][j]$$$ in the respective index of the segment tree for all $$$j$$$ ($$$1 \le j \le m-k+1$$$) initially. Now, to determine $$$DP[i][j]$$$ for each $$$j$$$, we want to subtract $$$sum(animal[i][max(j, x) \ldots min(j, x)+k-1])$$$ from the segment tree for all $$$x$$$ ($$$1 \le x \le m-k+1$$$). But it is infeasible to do this and add them back for every single $$$x$$$-s that has intersected areas. Here, we can use sliding window technique to improve it.
To determine $$$DP[i][1]$$$, we can manually subtract the first $$$k$$$ elements of $$$animal[i]$$$ from the segment tree like above. Let's assume that we're done with determining $$$DP[i][j-1]$$$. When we move on to determining $$$DP[i][j]$$$, we can see that $$$animal[i][j-1]$$$ is no longer in the range and thus should be added back to the segment tree. Precisely, all $$$DP[i-1][x]$$$-s where $$$x$$$ is within range $$$[max(1, j-k), j-1]$$$ are affected by this and must be added with $$$animal[i][j-1]$$$. Similarly, $$$animal[i][j+k-1]$$$ is now in the range and thus should be subtracted from all $$$DP[i-1][y]$$$-s where $$$y$$$ is within range $$$[j, j+k-1]$$$.
Each range update takes $$$O(\log{m})$$$ time, and this happens only two times for determining each $$$DP[i][j]$$$. The 'initial' work takes $$$O(k)$$$ time but it happens only once for each day. Therefore, it takes $$$O(m\log{m})$$$ time for each day and $$$O(nm\log{m})$$$ time in total.
Solution: $$$O(nm)$$$
It turns out that it's even possible without the segment tree. Of course, $$$O(nm\log{m})$$$ is intended to pass so you don't really need to implement this to solve the problem. Instead of segment tree, we'll use monotonic queue structure (the core idea for convex hull trick) to have the values in decreasing order from front to back. If you don't know what monotonic queue is, make sure you understand it first. You can read about it here.
We'll do basically the same thing we did for $$$O(nm\log{m})$$$ solution, but there are two major differences. First, we'll slide the window two times, one from left to right and the other one from right to left. Second, we'll only consider the values where the range of their indices intersects with the window, but only a part of them. We'll see how it works when sliding the window from left to right, then we can also do it in reverse direction.
We'll only consider all $$$DP[i-1][x]$$$ where $$$x$$$ is within range $$$[max(1, j-k+1), j]$$$. In other words, we only consider it when the intersected area is a prefix of the window. This means when we're about to determine $$$DP[i][j]$$$, $$$DP[i-1][j]$$$ (in fact, the actual value will be $$$DP[i-1][j] - sum(animal[i][j \ldots j+k-1])$$$) is inserted into the queue and $$$DP[i-1][j-k]$$$ is removed from the queue.
Now let's see how the 'real' values in the queue are changed while sliding the window. Since we'll only add the same value to all elements in the queue every time we slide the window, the order of the elements won't be changed, thus maintaining the monotone queue structure. However, we don't actually need to perform the 'add' action, simply because we can always calculate it in $$$O(1)$$$ time by calculating the sum of the animals between the index of that element (inclusive) and the window (exclusive). So to the 'real' value at the front of the queue, we can add $$$sum(animal[i \ldots i+1][j \ldots j+k-1])$$$ to determine $$$DP[i][j]$$$.
The exact same thing can be done in the reversed way, too. Now let's take back the prefix and suffix max we discussed in F1, so that we can check the cases when they do not intersect. We can see that each of these operations can be done in $$$O(m)$$$ for each day. Therefore, the whole process is performed in $$$O(nm)$$$ time.