跑步 - dp

题目大意：
给你一个网格，每个格子有个正权值，每次一个格子+1或者-1，然后求从左上角走到每个点路径上点权和最大值的和。n,m,q≤2000
题解：考虑修改一个位置会影响一部分，并且影响都是+1或者-1，因此只要考虑影响了多少个即可。
首先不难发现每一列受影响的是连续的一段，并且这连续的一段的上下端点是不减的，用一个BIT维护可以O(n2lgn)。
但是考虑dp[i,j]=max(dp[i,j−1],dp[i−1,j])+a[i,j]，并不关心dp
值到底是啥，而只关心其是否受影响，也就是dp[i,j]是否受影响只取决于dp[i,j−1]−dp[i−1,j]的正负变化，因此维护这个差即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<\"=\"<<x
#define sp <<\" \"
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
namespace INPUT_SPACE{
	const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
	char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
	inline int inn()
	{
		int x,ch;while((ch=gc())<\'0\'||ch>\'9\');
		x=ch^\'0\';while((ch=gc())>=\'0\'&&ch<=\'9\')
			x=(x<<1)+(x<<3)+(ch^\'0\');return x;
	}
	inline int GUD() { int c=0;while((c=gc())!=\'U\'&&c!=\'D\');return c; }
}using INPUT_SPACE::inn;using INPUT_SPACE::GUD;
const int N=2003;
int val[N][N],dp[N][N];
int main()
{
	int n=inn();lint ans=0;
	rep(i,1,n) rep(j,1,n)
		dp[i][j]=max(dp[i-1][j],dp[i][j-1])+inn(),
		ans+=dp[i][j],val[i][j]=dp[i-1][j]-dp[i][j-1];
	printf(\"%lld\\n\",ans);
	rep(curq,1,n)
	{
		int v=(GUD()==\'U\'?1:-1),x=inn(),y=inn();
		for(int i=y,l=x,r=x;i<=n;i++)
		{
			while(i>y&&l<=n)
			{
				val[l][i]-=v;
				if(val[l][i]+v>0&&v==1) l++;
				else if(val[l][i]+v>=0&&v==-1) l++;
				else break;
			}
			while(r<n)
			{
				val[r+1][i]+=v;
				if(val[r+1][i]-v>=0&&v==1) r++;
				else if(val[r+1][i]-v>0&&v==-1) r++;
				else break;
			}
			if(l>r) break;ans+=v*(r-l+1);
		}
		printf(\"%lld\\n\",ans);
	}
	return 0;
}