<h1>题目大意</h1>
现在有一个 $n\times m$ 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。
其中 $1 \leq n,m \leq 200$,区间个数 $k \leq 200$，区间最大的右端点 $ T \leq 40000$
<h1>题解</h1>
首先对于这个题目我们有一个很朴素的暴力，也就是记 $f_{i,x,y}$ 表示在时间点 $i$ 时自己在 $(x,y)$ 能走到的最远距离，转移只需要考虑这个时间点是否让钢琴不动：
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x',y'}+1\}$$
这里和下文中的 $x',y'$ 都默认是这个点能从哪里到来的位置。
显然这样的 dp 复杂度是 $O(Tn^2)$ 的，时间复杂度和空间复杂度都接受不了。
我们发现这个题目或许想让我们的复杂度与 $k$ 有关，于是我们可以考虑设 $f_{i,x,y}$ 表示在第 $i$ 个时间区间的时候，位置在 $(x,y)$ 能走的路径最大值。
不难发现这一段区间的决策可以拆成一段静止和一段不静止，所以我们可以得到转移方程：
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x',y'}+dis\}$$
这里 $dis$ 为点 $(x,y)$ 到点 $(x',y')$ 的曼哈顿距离，下文同理。
注意到这里可能的 $(x',y')$ 对最多有 $n$ 个，所以总复杂度为 $O(n^3k)$，需要考虑如何继续优化。
首先这个也可以滚动数组，于是我们设 $g = f_{i-1}$。式子可以重写成
$$f_{x,y} = min\{g_{x',y'}+dis\}$$
注意到每一段时间区间钢琴都是沿着水平线滑动的，也就是 $x$ 和 $y$ 至多改变一个。我们设这段区间转移时变化的维度是 $x$，忽略不变的那一维可以得到：
$$f_{x} = min\{g_{x+k}+|k|\}$$
这个式子在由 $f_x \to f_{x+1}$ 的过程中具有单调性，所以我们可以使用单调队列维护这一转移，时间复杂度变为 $O(n^2k)$，可以通过该题。
<h1>代码</h1>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 200+5;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int n,m,sx,sy,k,now,ans;
char strMAXN;
int f2[MAXN];
P q[MAXN];// pair<val,pos>
inline void calc(int x,int y,int len,int d){
d--;int head = 1,tail = 0;
for(int i = 1;x >= 1 && x <= n && y >= 1 && y <= m;x += dx[d],y += dy[d],++i){
if(strx == 'x') {head = 1,tail = 0;continue;}
while(head <= tail && q[tail].fi + i - q[tail].se < fnow^1[y]) tail--;
q[++tail] = MP(fnow^1[y],i);
if(q[tail].se - q[head].se > len) head++;
fnow[y] = q[head].fi + i - q[head].se;
ans = std::max(ans,fnow[y]);
}
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);
FOR(i,1,n) scanf("%s",str[i]+1);CLR(f,0xf3);
fnow[sy] = 0;
while(k--){
now ^= 1;int l,r,d;scanf("%d%d%d",&l,&r,&d);
if(d == 1) FOR(i,1,m) calc(n,i,r-l+1,d);
if(d == 2) FOR(i,1,m) calc(1,i,r-l+1,d);
if(d == 3) FOR(i,1,n) calc(i,m,r-l+1,d);
if(d == 4) FOR(i,1,n) calc(i,1,r-l+1,d);
}
printf("%dn",ans);
return 0;
}
