qaq
首先我们考虑其实这个条件就是要满足 \(f\) 严格比 \(g\) 大或 \(f\) 严格比 \(g\) 小。
在这里只讨论大于。
然后考虑到对于一个 \(i\) 如果不满足，我们可以把对应数组向右移一位看是否满足，如果还是不满足就无解了。
考虑对于现在满足的 \(i\) ，我们可以分别把两个指针向右移一位或者都移一位，所以很容易设计出状态及转移。
设 \(dp_{i,j}\) 表示 \(f\) 数组的指针到了第 \(i\) 位， \(g\) 数组的指针到了第 \(j\) 位能否匹配，转移：\(dp_{i,j} \ |= dp_{i-1,j} \ | \ dp_{i,j-1} \ | \ dp_{i-1,j-1}\)，分别对应上面的三种操作。
至此就 \(\Theta(nmq)\) 有35pts的高分了
#include<bits/stdc++.h>
using namespace std;
int c,n,m,q,kx,ky,x,y;
int a[2005],b[2005],ca[2005],cb[2005];
bool f[2005][2005],dp[2005][2005];
void work(){
if(a[1]<=b[1]||a[n]<=b[m]) f[n][m]=0;
else{
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j) f[i][j]=0;
}
f[1][1]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i]>b[j]) f[i][j]|=(f[i-1][j]|f[i][j-1]|f[i-1][j-1]);
}
}
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j) printf("%d",f[i][j]);
// printf("\n");
// }
// printf("\n");
}
if(a[1]>=b[1]||a[n]>=b[m]) dp[m][n]=0;
else{
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j) dp[i][j]=0;
}
dp[1][1]=1;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(a[j]<b[i]) dp[i][j]|=(dp[i-1][j]|dp[i][j-1]|dp[i-1][j-1]);
}
}
// for(int i=1;i<=m;++i){
// for(int j=1;j<=n;++j) printf("%d",dp[i][j]);
// printf("\n");
// }
// printf("\n");
}
printf("%d",f[n][m]|dp[m][n]);
}
int main(){
scanf("%d %d %d %d",&c,&n,&m,&q);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),ca[i]=a[i];
for(int i=1;i<=m;++i) scanf("%d",&b[i]),cb[i]=b[i];
work();
while(q--){
for(int i=1;i<=n;++i) a[i]=ca[i];
for(int i=1;i<=m;++i) b[i]=cb[i];
scanf("%d %d",&kx,&ky);
for(int i=1;i<=kx;++i) scanf("%d %d",&x,&y),a[x]=y;
for(int i=1;i<=ky;++i) scanf("%d %d",&x,&y),b[x]=y;
work();
}
return 0;
}
然后感觉这个东西好像很熟悉，这不就是网格走路吗。
考虑一个 \(n\times m\) 的网格，每次可以向右、下、右下三个方向走，中间如果小于等于就不可走，问能否从起点到达终点。
既然都分析成这样了，我们考虑怎么优化掉这个 \(n\times m\)。
看一眼特殊性质，好奇怪啊，跟max和min有什么关系。仔细想一想，发现我确实只需要知道两个数列max和min的关系，因为max和min的讨论一定更加极限，是最后的必要条件，到达性一定可以通过max和min转移过来,换句话说，它们两个是充要条件。可以走到一定没有全堵住的行和全堵住的列，而全堵住的最有可能的就是max对min，反之亦然。
然后考虑我现在要保证严格大于，那么我的数列一定有 \(f_{max}>g_{max}\) 和 \(f_{min}>g_{min}\) 。
结合上面的网格，我们思考其实就是如果 $f_{min} \leq g_{min} $ 或者 \(f_{max} \leq g_{max}\) ，那么一定不可到达的。
所以我们其实可以逐步缩小范围，就是你考虑如果从起点可以走到 \(max,min\) 这样的交点，然后从这个点又可以走到终点，那么就可以到达。
具体地，每次选择当前区间内 \(f_{max}\) 和 \(g_{min}\) ，如果当前满足条件就向左向下缩，不断递归，直到有一个不满足的或者是到达了目标行或目标列。
于是我们成功将问题转化为两部分的到达性处理，而这两部分的到达性问题我们又可以向内分治，再做一个前缀最大最小，缩的次数最多是 \(n+m\) 于是时间复杂度转化为 \(\Theta(q \ (n+m) )\)。
qaq给我调破防了
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int c,n,m,q,kx,ky,x,y;
int a[MAXN],b[MAXN],ca[MAXN],cb[MAXN];
struct W{
int pos,val;
};
W preai[MAXN],preaa[MAXN];//f的前缀最小最大
W prebi[MAXN],preba[MAXN];//g的前缀最小最大
W ai[MAXN],aa[MAXN];//f的后缀最小最大
W bi[MAXN],ba[MAXN];//g的后缀最小最大
void pre(){
preaa[0].val=-1;preba[0].val=-1;
preai[0].val=1e9+1;prebi[0].val=1e9+1;
aa[n+1].val=-1;ba[m+1].val=-1;
ai[n+1].val=1e9+1;bi[m+1].val=1e9+1;
for(int i=1;i<=n;++i){
if(preai[i-1].val>a[i]) preai[i].pos=i,preai[i].val=a[i];
else preai[i]=preai[i-1];
if(preaa[i-1].val<a[i]) preaa[i].pos=i,preaa[i].val=a[i];
else preaa[i]=preaa[i-1];
}
for(int i=n;i>=1;--i){
if(ai[i+1].val>a[i]) ai[i].pos=i,ai[i].val=a[i];
else ai[i]=ai[i+1];
if(aa[i+1].val<a[i]) aa[i].pos=i,aa[i].val=a[i];
else aa[i]=aa[i+1];
}
for(int i=1;i<=m;++i){
if(prebi[i-1].val>b[i]) prebi[i].pos=i,prebi[i].val=b[i];
else prebi[i]=prebi[i-1];
if(preba[i-1].val<b[i]) preba[i].pos=i,preba[i].val=b[i];
else preba[i]=preba[i-1];
}
for(int i=m;i>=1;--i){
if(bi[i+1].val>b[i]) bi[i].pos=i,bi[i].val=b[i];
else bi[i]=bi[i+1];
if(ba[i+1].val<b[i]) ba[i].pos=i,ba[i].val=b[i];
else ba[i]=ba[i+1];
}
}
bool check1(int x,int y,int ac){
if(ac){
if(x==1||y==1) return true;
if(preai[x-1].val>prebi[y-1].val) return check1(x,prebi[y-1].pos,ac);
if(preaa[x-1].val>preba[y-1].val) return check1(preaa[x-1].pos,y,ac);
return false;
}
else{
if(x==1||y==1) return true;
if(preai[x-1].val<prebi[y-1].val) return check1(preai[x-1].pos,y,ac);
if(preaa[x-1].val<preba[y-1].val) return check1(x,preba[y-1].pos,ac);
return false;
}
return 0;
}
bool check2(int x,int y,int ac){
if(ac){
if(x==n||y==m) return true;
if(ai[x+1].val>bi[y+1].val) return check2(x,bi[y+1].pos,ac);
if(aa[x+1].val>ba[y+1].val) return check2(aa[x+1].pos,y,ac);
return false;
}
else{
if(x==n||y==m) return true;
if(ai[x+1].val<bi[y+1].val) return check2(ai[x+1].pos,y,ac);
if(aa[x+1].val<ba[y+1].val) return check2(x,ba[y+1].pos,ac);
return false;
}
}
bool work(){
if(a[1]<b[1]&&a[n]<b[m]){
if(preaa[n].val>=preba[m].val||preai[n].val>=prebi[m].val) return false;
return check1(preai[n].pos,preba[m].pos,0)&&check2(preai[n].pos,preba[m].pos,0);
}
else if(a[1]>b[1]&&a[n]>b[m]){
if(preaa[n].val<=preba[m].val||preai[n].val<=prebi[m].val) return false;
return check1(preaa[n].pos,prebi[m].pos,1)&&check2(preaa[n].pos,prebi[m].pos,1);
}
return false;
}
int main(){
scanf("%d %d %d %d",&c,&n,&m,&q);
for(int i=1;i<=n;++i) preai[i].val=2e9;for(int i=1;i<=m;++i) prebi[i].val=2e9;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),ca[i]=a[i];
for(int i=1;i<=m;++i) scanf("%d",&b[i]),cb[i]=b[i];
pre();
printf("%d",work());
while(q--){
for(int i=1;i<=n;++i) a[i]=ca[i];
for(int i=1;i<=m;++i) b[i]=cb[i];
scanf("%d %d",&kx,&ky);
for(int i=1;i<=kx;++i) scanf("%d %d",&x,&y),a[x]=y;
for(int i=1;i<=ky;++i) scanf("%d %d",&x,&y),b[x]=y;
pre();
printf("%d",work());
}
return 0;
}