F2. Animal Observation (hard version)

F2. Animal Observation (hard version)

time limit per test：3 seconds memory limit per test：512 megabytes inputstandard input outputstandard output

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 The first line contains three integers n, m, and k (1≤n≤50, 1≤m≤2⋅10^4^, 1≤k≤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 Print one integer – the maximum number of animals that can be observed.

input

4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4

output

25

input

3 3 1
1 2 3
4 5 6
7 8 9

output

31

input

3 3 2
1 2 3
4 5 6
7 8 9

output

44

input

3 3 3
1 2 3
4 5 6
7 8 9

output

45

题目大意

给出n，m，k，分别表示有n天m个位置，一个相机可以拍到连续的 k 个位置，他有两个相机每个相机能放在一个位置两天，并且这两个相机分别只能在奇数天或者偶数天放出去拍摄，现在知道了这n天每天这m个位置会出现的动物的数量，问你最多可以拍到多少个动物，同一天的一个位置只能计算一次。

解题思路

为了方便统计放到某个位置可以拍到的数量和，我们先统计每一行的前缀和，这样计算连续k的区间的和的话就比较方便了，我用一个dp[i][j] 记录相机第 i 天放到第 j 个位能够拍到的最多数量，然后下一天加上上一天最多的位置，就可以了。当让你计算前一天最多的位置的时候要先减去，前一天在这个位置排到的，然后统计完以后还要在加上这个位置的数量，这个过程个一用一个线段树去维护一个区间最大值就可以了。 举个栗子看下吧 4 5 2 0 2 1 1 0 0 0 3 1 2 1 0 4 3 1 3 3 0 0 4 首先肯定是预处理第一天的所以第一天的位置分别是2 6 6 4 2 这时候去构建一课线段树，树的最下面元素分别是2 6 6 4 2 当计算第二天的时候 如果相机放到第一个位置，那么首先线段树最先面的第一个位置的值要减去第二天在第1和第2个位置的值，即2-0-0；因为第二天相机放在第一位置的时候也能拍到这两个位置的值，和第一天的这个位置重复了，所以要先减去，之后再看看第一天放到哪个位置的数量最多，dp[2][1]=tre[1]+放到这个位置连续两天拍摄的数量和。tre[1]是上一天这m个位置中对多的 然后我们要在前一天的这个位置上加上 a[i][j]；因为当第二天这个相机放到第二个位置的时候，第一天可以拍到的第二天的第一个位置这个位置就不会重复，所以把之前减去了再加上。这时候再将第 k+j 这个位置的值减去a[i][k+j]，因为第二天的时候放到第二个位置的时候，前一天放到这个位置的时候已经拍到了这个位置。然后依次类推下去就行了

代码

#include<bits/stdc++.h>
using namespace std;

int sum[55][20010];//记录前缀和 
int a[55][20010];
int tre[80040]; //存值 
int laz[80040];//lazy标记 
int dp[55][20010];//记录第几题放到第几个位置能拍到最多的数量 
void up_down(int x,int l,int r)
{//将 lazy数组的值向下传递 
    laz[x<<1]+=laz[x];
    laz[x<<1|1]+=laz[x];
    tre[x<<1]+=laz[x];
    tre[x<<1|1]+=laz[x];
    laz[x]=0;
    return;
}
//进行更新 
void up(int x,int l,int r,int ql,int qr,int k)
{
    if(ql<=l&&r<=qr)
    {
        tre[x]+=k;
        laz[x]+=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(laz[x]) up_down(x,l,r);
    if(ql<=mid) up(x<<1,l,mid,ql,qr,k);
    if(qr>mid) up(x<<1|1,mid+1,r,ql,qr,k);
    tre[x]=max(tre[x<<1],tre[x<<1|1]);
}
//求区间和 
int Sum(int xl,int yl,int yr)
{
    yl--;
    return sum[xl][yr]-sum[xl][yl]+sum[xl+1][yr]-sum[xl+1][yl];
}

int main()
{
    ios::sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            sum[i][j]=a[i][j]+sum[i][j-1];//记录前缀和 
        }
    }
    for(int i=1;i<=m;i++)//更新第一天区间 
    {
        dp[1][i]=Sum(1,i,min(i+k-1,m));//连续的k个位置依次向后移动 
    }
    for(int i=2;i<=n;i++)
    {    //每天开始的时候都要初始化 
        memset(tre,0,sizeof tre);
        memset(laz,0,sizeof laz);
        for(int j=1;j<=m;j++)//更新线段树的值 
        {
            up(1,1,m,j,j,dp[i-1][j]);
        }
        for(int j=1;j<=k;j++)
        {//减去前一天放在第一个位置和今天放在第一个位置重复拍到的数量 
            up(1,1,m,1,j,-a[i][j]);
        } 
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=tre[1]+Sum(i,j,min(j+k-1,m));//前一天能拍到的最大值加上今天在这个位置拍到的数量 
            up(1,1,m,max(j-k+1,1),j,a[i][j]);//在前天这个位置排到的数量加上这个位置 
            if(j+k<=m)                        //因为相机放在第二个位置，就拍不到第一个位置了所以第一个位置就不会重复了 
            {
                up(1,1,m,j+1,j+k,-a[i][j+k]);//要放到下个位置的时候，减去如果前一天在下个位置已经排到的 
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=m;i++) ans=max(ans,dp[n][i]);//输出最大值 
    cout<<ans<<"\n";
    return 0;
}