做法一
现考虑一个人的情况。设 \(f_{i,j,0/1}\) 表示从 \((i,j)\) 开始沿横/竖方向走的最大距离。
走到下一个位置相当于在其中一个数组中向左/右找第一个大于某值的位置。可以用 ST 表或线段树解决。
若使用线段树解决，考虑将其分为 \(\mathcal O(\log n)\) 个区间，并找到最左/右的可能区间递归进去，复杂度仍为 \(O(\log n)\)。
发现由于所需的状态实际上不会很多，所以可以使用记忆化，然后就过了。复杂度 \(\mathcal O(玄学)\)。
#include <map>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
using ll=long long;
const int N=5e4+5;
int a[N],b[N];
struct Seg{
int mx[N<<2];
#define lc(p) ((p)<<1)
#define rc(p) ((p)<<1|1)
void build(int p,int l,int r,int a[]){
if(l==r){
mx[p]=a[l];
return ;
}
int mid=(l+r)>>1;
build(lc(p),l,mid,a);
build(rc(p),mid+1,r,a);
mx[p]=max(mx[lc(p)],mx[rc(p)]);
}
int queryL(int p,int l,int r,int x,int v){
if(l>=x||mx[p]<=v) return -1;
if(l==r) return l;
int mid=(l+r)>>1;
int ind=queryL(rc(p),mid+1,r,x,v);
if(ind!=-1) return ind;
return queryL(lc(p),l,mid,x,v);
}
int queryR(int p,int l,int r,int x,int v){
if(r<=x||mx[p]<=v) return -1;
if(l==r) return l;
int mid=(l+r)>>1;
int ind=queryR(lc(p),l,mid,x,v);
if(ind!=-1) return ind;
return queryR(rc(p),mid+1,r,x,v);
}
#undef lc
#undef rc
}tr1,tr2;
map<int,ll> mp[N][2];
int n,m;
ll dfs(int x,int y,int d){
if(mp[x][d].count(y)) return mp[x][d][y];
if(d==1){
ll ans1=tr1.queryL(1,1,n,x,b[y]),ans2=tr1.queryR(1,1,n,x,b[y]);
if(ans1==-1) ans1=x-1;
else ans1=(x-ans1)+dfs(ans1,y,d^1);
if(ans2==-1) ans2=n-x;
else ans2=(ans2-x)+dfs(ans2,y,d^1);
return mp[x][d][y]=max(ans1,ans2);
}
else{
ll ans1=tr2.queryL(1,1,m,y,a[x]),ans2=tr2.queryR(1,1,m,y,a[x]);
if(ans1==-1) ans1=y-1;
else ans1=(y-ans1)+dfs(x,ans1,d^1);
if(ans2==-1) ans2=m-y;
else ans2=(ans2-y)+dfs(x,ans2,d^1);
return mp[x][d][y]=max(ans1,ans2);
}
}
signed main(){
int q;
io>>n>>m>>q;
for(int i=1;i<=n;++i) io>>a[i];
for(int i=1;i<=m;++i) io>>b[i];
tr1.build(1,1,n,a);tr2.build(1,1,m,b);
for(int i=1;i<=q;++i){
int x,y;io>>x>>y;
printf("%lld\n",max(dfs(x,y,0),dfs(x,y,1)));
}
return 0;
}
做法二（推荐）
考虑分治。对于一个矩形，在其最外侧加上一层权值为 \(-1\) 的边框（抵消走出的贡献）。则每次考虑选出边权最大的边，其只能一直直走，若其两端与外边框所交位置的答案分别为 \(a,b\)，则编号为 \(x\) 的点的答案为 \(\max(a+x-l,b+r-x)\)，然后以该线为界，分成左右矩形，然后选择一边递归即可。注意到我们只需要记录好 \(\max\) 函数的参数即可。用 ST 表找最大值，复杂度 \(\mathcal O(n\log n+m\log m+q(n+m))\)
标签：return,int,ans1,ans2,dfs,ind,Abduction,誘拐,JOISC2017j From： https://www.cnblogs.com/pref-ctrl27/p/16976984.html