Codeforces Round #620 (Div. 2) F2. Animal Observation (hard version)

题目链接
题目大意：给你一个 $n\ast m$n∗m的矩阵，你可以在每行放置一个 $2\ast k$2∗k的矩形框，问你被矩形框 ，框中的数的和最大值是多少。每个数只计算一次。
思路：用 $dp\left[i\right]\left[j\right]$dp[i][j]，表示第 $i$i个矩形框放在第 $j$j列的时候的最大值。
暴力的转移是很显然的：枚举上一次的所有情况即可。
优化的话可以用线段树优化成 $log$log的转移复杂度。具体实现是：
当前第 $i$i行，第 $j$j列的元素显然只会和放置在 $i-1$i−1行的 $\left[max\right(j-k+1,1),j]$[max(j−k+1,1),j]列的 矩形框产生重合的部分，转移的时候，我们要去掉所有重合的部分。
那么具体到每个元素的话， $a_{i,j}$ai,j​显然只会在从 $dp[i-1]\left[x\right],x\in \left[max\right(1,j-k+1),j]$dp[i−1][x],x∈[max(1,j−k+1),j]转移的时候被去掉。那我们显然直接在线段树上区间更新即可。由于窗口大小为 $k$k，所以每次要记得加上已经离开窗口的元素 ，在把进加入窗口的元素给去掉即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10;
#define fi first
#define se second
#define pb push_back
int n,m,a[55][N],k;
LL s[55][N],dp[55][N];
LL ans;
LL laz[N<<2],t[N<<2];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
void pd(int o,int l,int r){
  t[ls]+=laz[o];
  t[rs]+=laz[o];
  laz[ls]+=laz[o];
  laz[rs]+=laz[o];
  laz[o]=0;
  return ;
}
void ud(int o,int l,int r,int x,int y,int d){
  if(x<=l&&y>=r){
    t[o]+=d;
    laz[o]+=d;
    return ;
  }
  if(laz[o])pd(o,l,r);
  if(x<=mid)ud(ls,l,mid,x,y,d);
  if(y>mid)ud(rs,mid+1,r,x,y,d);
  t[o]=max(t[ls],t[rs]);
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
      s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
    }
  }
  auto get =[&](int r1,int c1,int r2,int c2){
    return s[r2][c2]-s[r2][c1-1]-s[r1-1][c2]+s[r1-1][c1-1];
  };
  for(int i=1;i<=m;i++){
    dp[1][i]=get(1,i,min(n,2),min(m,i+k-1));
  }
  for(int i=2;i<=n;i++){
    memset(t,0,sizeof t);
    memset(laz,0,sizeof laz);
    for(int j=1;j<=m;j++)ud(1,1,m,j,j,dp[i-1][j]);
    for(int j=1;j<=k;j++)ud(1,1,m,1,j,-a[i][j]);
    for(int j=1;j<=m;j++){
      dp[i][j]=t[1]+get(i,j,min(n,i+1),min(m,j+k-1));
      ud(1,1,m,max(j-k+1,1),j,a[i][j]);
      if(j+k<=m)ud(1,1,m,j+1,j+k,-a[i][j+k]);
    }
  }
  for(int i=1;i<=m;i++)ans=max(ans,dp[n][i]);
  cout<<ans<<'\n';
  return 0;
}