模拟赛里搬了这个题。我愤怒写了 $3$ 小时。

solution

暴力的把 DAG 连出来跑最长路显然是很神人的。

直接列一个暴力 dp 逐行转移。在走动里面只有转向的那些拐点是重要的。只需要维护一下行和列的最大值就行了。无修所以上个 ST 表。

然后因为多测会搜重状态，开 map 记忆化一下就行了。

考虑你每一次询问的时候扩展到的点应该围成了一个矩形。

假设当前已经扩展了 $\dfrac{N}{\sqrt{Q}}$ 步。那么从该点再进一步的一步至少会覆盖之前未覆盖的区域面积量 $\ge \dfrac{N}{\sqrt{Q}}$。

因为从深度 $\dfrac{N}{\sqrt{Q}}$ 的位置继续沿某个方向前进，直到再次转弯或到边界。由于已经走过的深度大于 $\dfrac{N}{\sqrt{Q}}$，这个前进段的长度必包含一个连续长度至少为 $\dfrac{N}{\sqrt{Q}}$ 的直段。沿该直段所覆盖的格点可看成一个 $1\times \dfrac{N}{\sqrt{Q}}$ 的矩形区域。因此该步骤至少覆盖面积 $\dfrac{N}{\sqrt{Q}}$。

所以状态数是 $O(N\sqrt{Q})$ 的。复杂度 $O(N\sqrt{Q}\log{N})$。submission。

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void out(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=5e4+5,V=16,mod=196884;
array<int,N>a,b;array<array<int,N>,V>ma,mb;
int n,m,q;
int Ma(int l,int r){
    int k=__lg(r-l+1);
    return max(ma[k][l],ma[k][r-(1<<k)+1]);
}
int Mb(int l,int r){
    int k=__lg(r-l+1);
    return max(mb[k][l],mb[k][r-(1<<k)+1]);
}
int id(int x,int y,int d){return (x*m+y+n*m*d);}
__gnu_pbds::gp_hash_table<int,int>mp;
int Find(int x,int y,int d){
    // cout<<x<<" "<<y<<" "<<d<<"\n";
    int st=id(x,y,d);
    if(mp.find(st)!=mp.end())return mp[st];
    if(d==0){
        // puts("fi");
        int l=0,r=x-1,lp=0,rp=0;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(Ma(mid,x-1)<b[y])r=mid-1;
            else l=mid;
        }lp=l,l=x+1,r=n+1;
        while(l<r){
            int mid=(l+r)>>1;
            if(Ma(x+1,mid)<b[y])l=mid+1;
            else r=mid;
        }rp=l;
        if(!lp&&rp==n+1)return mp[st]=max(x-1,n-x);
        if(!lp)return mp[st]=max(x-1,Find(rp,y,1)+rp-x);
        if(rp==n+1)return mp[st]=max(Find(lp,y,1)+x-lp,n-x);
        return mp[st]=max(Find(lp,y,1)+x-lp,Find(rp,y,1)+rp-x);
    }else{
        // puts("se");
        int l=0,r=y-1,lp=0,rp=0;
        // cout<<l<<" "<<r<<"\n";
        while(l<r){
            // cout<<l<<" "<<r<<"\n";
            int mid=(l+r+1)>>1;
            if(Mb(mid,y-1)<a[x])r=mid-1;
            else l=mid;
        }lp=l,l=y+1,r=m+1;
        // cout<<l<<" "<<r<<"\n";
        while(l<r){
            // cout<<l<<" "<<r<<"\n";
            int mid=(l+r)>>1;
            if(Mb(y+1,mid)<a[x])l=mid+1;
            else r=mid;
        }rp=l;
        if(!lp&&rp==m+1)return mp[st]=max(y-1,m-y);
        if(!lp)return mp[st]=max(y-1,Find(x,rp,0)+rp-y);
        if(rp==m+1)return mp[st]=max(Find(x,lp,0)+y-lp,m-y);
        return mp[st]=max(Find(x,rp,0)+rp-y,Find(x,lp,0)+y-lp);
    }
}
signed main(){
    // freopen("froggay.in","r",stdin);
    // freopen("froggay.out","w",stdout);
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)b[i]=read();
    a[0]=a[n+1]=b[0]=b[m+1]=INT_MAX;ma[0]=a,mb[0]=b;
    for(int i=1;i<V;i++){
        for(int j=0;j+(1<<i)-1<=n+1;j++){
            ma[i][j]=max(ma[i-1][j],ma[i-1][j+(1<<(i-1))]);
        }for(int j=0;j+(1<<i)-1<=m+1;j++){
            mb[i][j]=max(mb[i-1][j],mb[i-1][j+(1<<(i-1))]);
        }
    }while(q--){
        int s=read(),t=read();
        // cout<<Find(2,1,0)<<"\n";
        // cout<<s<<" "<<t<<"\n";
        // if(a[s]<b[t])cout<<Find(s,t,0)<<"\n";
        // else cout<<Find(s,t,1)<<"\n";
        // cout<<Find(s,t,0)<<" "<<Find(s,t,1)<<"\n";
        cout<<max(Find(s,t,0),Find(s,t,1))<<"\n";
    }//cout<<"eraesteyr"<<endl;
    return 0;
}