A好像做过，但是二进制分组是带log的。
B题根据以前做过的一道题的想法，很快就想到行列分开处理。
这样子我们就要求一些行和一些列交点的最短路，可以线段树上二分+分类讨论处理。
然而细节非常多，调到考试结束都没写出来。
放一个过了loj数据的代码：
#include<bits/stdc++.h>
using namespace std;
#define N 4000010
struct sgt{
int mn[N],mx[N];
void mod(int o,int l,int r,int x,int y){
if(l==r){
mn[o]=mx[o]=y;
return;
}
int md=(l+r)/2;
if(x<=md)
mod(o*2,l,md,x,y);
else
mod(o*2+1,md+1,r,x,y);
mn[o]=min(mn[o*2],mn[o*2+1]);
mx[o]=max(mx[o*2],mx[o*2+1]);
}
int e1(int o,int l,int r,int x,int y){
if(mn[o]>y||l>r)
return -1;
if(l==r)
return l;
int md=(l+r)/2;
if(x>md)
return e1(o*2+1,md+1,r,x,y);
int po=e1(o*2,l,md,x,y);
if(po==-1)
return e1(o*2+1,md+1,r,x,y);
return po;
}
int e2(int o,int l,int r,int x,int y){
if(mn[o]>y||l>r)
return -1;
if(l==r)
return l;
int md=(l+r)/2;
if(x<=md)
return e2(o*2,l,md,x,y);
int po=e2(o*2+1,md+1,r,x,y);
if(po==-1)
return e2(o*2,l,md,x,y);
return po;
}
int qu(int o,int l,int r,int x,int y){
if(r<x||y<l)
return -1e9;
if(x<=l&&r<=y)
return mx[o];
int md=(l+r)/2;
return max(qu(o*2,l,md,x,y),qu(o*2+1,md+1,r,x,y));
}
int qm(int o,int l,int r,int x,int y){
if(r<x||y<l)
return 1e9;
if(x<=l&&r<=y)
return mn[o];
int md=(l+r)/2;
return min(qm(o*2,l,md,x,y),qm(o*2+1,md+1,r,x,y));
}
}h,l;
int n,m,q,mh[N],ml[N];
int main(){
//freopen("snow.in","r",stdin);
//freopen("snow.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
int ct=0,qc=0;
while(q--){
int op;
scanf("%d",&op);
ct--;
if(op==2){
int x;
scanf("%d",&x);
h.mod(1,1,m,x,ct);
mh[x]=ct;
}
if(op==1){
int x;
scanf("%d",&x);
l.mod(1,1,n,x,ct);
ml[x]=ct;
}
if(op==3){
int x1,y1,x2,y2,k;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
if(x1==x2&&y1==y2){
puts("0");
continue;
}
k+=ct;
int v1=min(ml[x1],mh[y1]),v2=min(ml[x2],mh[y2]);
if(v1>k||v2>k)
puts("-1");
else{
int a=min(x1,x2),b=max(x1,x2),c=min(y1,y2),d=max(y1,y2);
int v1=l.qu(1,1,n,a,b),v2=h.qu(1,1,m,c,d),ans=1e9;
if(ml[x1]<=k&&mh[y1]<=k&&ml[x2]<=k&&mh[y2]<=k){
printf("%d
",d-c+b-a);
continue;
}
if((v1<=k&&v1>-1e9)||(v2<=k&&v2>-1e9)){
printf("%d
",d-c+b-a);
continue;
}
v1=l.qm(1,1,n,a,b);
v2=h.qm(1,1,m,c,d);
if(v1<=k&&v2<=k){
printf("%d
",d-c+b-a);
continue;
}
if((mh[y1]<=k&&ml[x2]<=k)||(ml[x1]<=k&&mh[y2]<=k)){
printf("%d
",d-c+b-a);
continue;
}
if(ml[x1]>k){
int p1=l.e1(1,1,n,x1+1,k),p2=l.e1(1,1,n,x2+1,k);
if(p1==p2){
int p3=l.e2(1,1,n,x1-1,k);
if(p1!=-1)
ans=min(ans,d-c+(p1-x1+p1-x2));
if(p3!=-1)
ans=min(ans,d-c+(x1-p3+x2-p3));
if(ans!=1e9)
printf("%d
",ans);
else puts("-1");
}
else{
printf("%d
",d-c+b-a);
continue;
}
}
else{
int p1=h.e1(1,1,m,y1+1,k),p2=h.e1(1,1,m,y2+1,k);
if(p1==p2){
int p3=h.e2(1,1,m,y1-1,k);
if(p3!=-1)
ans=min(ans,b-a+(y1-p3+y2-p3));
if(p1!=-1)
ans=min(ans,b-a+(p1-y1+p1-y2));
if(ans!=1e9)
printf("%d
",ans);
else puts("-1");
}
else{
printf("%d
",d-c+b-a);
continue;
}
}
}
}
}
}