yjz对这道题的评价是：
“这是一道很基础的题。”
LOJ题目页面传送门
题意见LOJ。
刚看完题以为又是个甚么实时维护最短路的神仙科技。其实所谓的神仙科技都是不存在的。
注意到，任意时刻，对于任意最大踏雪深度，可踏的区域一定是一些行和一些列的并。这样把可踏区域给提出来就好办多了。
于是我们维护每行每列的最后一次被清空的时间戳（如果没有被清空过就是(0)，因为一开始是空的）(x)，设当前时间戳为(i)，那么这行/列都可踏当且仅当(i-xleq k_iLeftrightarrow xgeq i-k_i)。
考虑如何求(A_1(r_1,c_1))到(A_2(r_2,c_2))的最短路。需要分一分情况（可能同时满足几个情况）：
-
(A_1,A_2)所在行可踏。那么分成两种情况：
- (A_1,A_2)之间没有可踏列。那么只需要找离(A_1)（或(A_2)）最近的两侧的可踏列，算一下距离更新答案即可；
- (A_1,A_2)之间有可踏列。那么显然直接把距离更新为(A_1,A_2)的曼哈顿距离即可（这达到了下限）。
为了方便写，我们不论是情况(1.1)还是情况(1.2)都按照情况(1.1)的方法来处理，这样不用分类，而且正确性不变。
需要注意的是，可能有一些列，它并不是可踏列，但是在(A_1)到(A_2)的那一段截下来每处所在行都是可踏行，这样也是可以走的。这个异常好处理，注意到如果有这样的情况，那么在(A_1)到(A_2)段的任意列都可以走，那么直接把距离更新为(A_1,A_2)的曼哈顿距离即可；
-
(A_1,A_2)所在列可踏。与情况(1)类似；
-
(A_1)所在行可踏，(A_2)所在列可踏。这样可以直接把距离更新为(A_1,A_2)的曼哈顿距离，一种可行的方案是，先从(A_1)走到(A_1)所在行(A_2)所在列交点，再走到(A_2)；
-
(A_1)所在列可踏，(A_2)所在行可踏。与情况(3)类似。
那么唯一的难点就在于怎么求“离(A_1)（或(A_2)）最近的两侧的可踏列”。容易发现这其实就是求区间中(c_1)的前驱后继（区间基于时间戳，是([i-k_i,i))，若某时间有清空列的操作，则此处有值为清空的列）。zszz，线段树套平衡树求区间前驱后继是可以做到(mathrm O!left(log^2n
ight))（假设(n,m)同阶）的，我们也可以二分+可持久化平衡树（虽然我还不会）求区间排名做到(mathrm O!left(log^2n
ight))。不过通过看题解可知是有1log方法的。
考虑交换定义域和值域（老套路了），基于列的编号维护最后一次被清空的时间戳。这样我们可以维护一棵线段树，单点修改，至于求前驱后继，以前驱为例，设要求(x)的前驱，我们从右往左把区间([1,x])剖成线段树上的若干区间，对第一个剖出来的（即最右边的）有可踏列的（判断这个只需要维护时间戳的(max)）区间线段树二分即可。哦对之前忘了说了，“在(A_1)到(A_2)的那一段截下来每处所在行都是可踏行”这个东西也要维护，现在正好有基于列编号的线段树了，顺带维护一下区间(min)即可。
至于为啥交换定义域和值域就可以少一个(log)？这是一个哲学问题。其实很简单，因为只有要求的东西在定义域上，我们才可以使劲往左/右靠，从而实现将二分与DS操作合体。
时间复杂度(mathrm O(qlog n))。（常数异常大别嫌弃）
代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1000000;
int n,m,qu;
struct segtree{//基于行/列编号的线段树
struct node{int l,r,mx,mn;}nd[N<<2];
#define l(p) nd[p].l
#define r(p) nd[p].r
#define mx(p) nd[p].mx
#define mn(p) nd[p].mn
void bld(int l,int r,int p=1){
l(p)=l;r(p)=r;mx(p)=mn(p)=0;//一开始都是0
if(l==r)return;
int mid=l+r>>1;
bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
}
void init(int r){bld(1,r);}
void sprup(int p){mx(p)=max(mx(p<<1),mx(p<<1|1));mn(p)=min(mn(p<<1),mn(p<<1|1));}
void chg(int x,int v,int p=1){//单点修改
if(l(p)==r(p))return mx(p)=mn(p)=v,void();
int mid=l(p)+r(p)>>1;
chg(x,v,p<<1|(x>mid));
sprup(p);
}
int at(int x){//单点查询
int p=1;
while(l(p)<r(p)){
int mid=l(p)+r(p)>>1;
p=p<<1|(x>mid);
}
return mx(p);
}
int _mn(int l,int r,int p=1){//区间最小值
if(l<=l(p)&&r>=r(p))return mn(p);
int mid=l(p)+r(p)>>1,res=inf;
if(l<=mid)res=min(res,_mn(l,r,p<<1));
if(r>mid)res=min(res,_mn(l,r,p<<1|1));
return res;
}
int prv(int l,int r,int lim,int p=1){//前驱
if(l<=l(p)&&r>=r(p))
if(mx(p)<lim)return 0;//没有的话滚蛋
else{//有的话线段树二分
while(l(p)<r(p)){
if(mx(p<<1|1)>=lim)p=p<<1|1;
else p=p<<1;
}
return l(p);
}
int mid=l(p)+r(p)>>1;
if(r>mid){//从右往左
int res=prv(l,r,lim,p<<1|1);
if(res)return res;
}
if(l<=mid){
int res=prv(l,r,lim,p<<1);
if(res)return res;
}
return 0;
}
int nxt(int l,int r,int lim,int p=1){//后继，同上
if(l<=l(p)&&r>=r(p))
if(mx(p)<lim)return 0;
else{
while(l(p)<r(p)){
if(mx(p<<1)>=lim)p=p<<1;
else p=p<<1|1;
}
return l(p);
}
int mid=l(p)+r(p)>>1;
if(l<=mid){
int res=nxt(l,r,lim,p<<1);
if(res)return res;
}
if(r>mid){
int res=nxt(l,r,lim,p<<1|1);
if(res)return res;
}
return 0;
}
}segt_r/*行*/,segt_c/*列*/;
int main(){
cin>>n>>m>>qu;
segt_r.init(n);segt_c.init(m);//初始化
for(int i=1;i<=qu;i++){
int tp,a,b,c,d,e;
scanf("%d%d",&tp,&a);
if(tp==1)segt_r.chg(a,i);//单点修改
else if(tp==2)segt_c.chg(a,i);//单点修改
else{
scanf("%d%d%d%d",&b,&c,&d,&e);
int ans=inf;
int r_a=segt_r.at(a),r_c=segt_r.at(c),c_b=segt_c.at(b),c_d=segt_c.at(d);
if(r_a>=i-e&&c_d>=i-e||c_b>=i-e&&r_c>=i-e){printf("%d
",abs(a-c)+abs(b-d));continue;}//情况3,4
if(c_b>=i-e&&c_d>=i-e){//情况2
if(segt_c._mn(min(b,d),max(b,d))>=i-e){printf("%d
",abs(a-c)+abs(b-d));continue;}//需要注意的是
int prv=segt_r.prv(1,a,i-e),nxt=segt_r.nxt(a,n,i-e);
if(prv)ans=min(ans,abs(prv-a)+abs(prv-c)+abs(b-d));//前驱更新答案
if(nxt)ans=min(ans,abs(nxt-a)+abs(nxt-c)+abs(b-d));//后继更新答案
}
if(r_a>=i-e&&r_c>=i-e){//情况1
if(segt_r._mn(min(a,c),max(a,c))>=i-e){printf("%d
",abs(a-c)+abs(b-d));continue;}//需要注意的是
int prv=segt_c.prv(1,b,i-e),nxt=segt_c.nxt(b,m,i-e);
if(prv)ans=min(ans,abs(prv-b)+abs(prv-d)+abs(a-c));//前驱更新答案
if(nxt)ans=min(ans,abs(nxt-b)+abs(nxt-d)+abs(a-c));//后继更新答案
}
printf("%d
",ans==inf?-1:ans);
}
}
return 0;
}