测试点 $1\sim7$
考虑将问题转化。
对于 $\forall1\leq i,j\leq l_0$ 均有 $(f_i-g_i)(f_j-g_j)>0$，即对于 $\forall1\leq i\leq l_0$，有 $f_i>g_i$ 或 $f_i<g_i$。
不妨设 $f_i=x_a,g_i=y_b$。则对于 $f_{i+1},g_{i+1}$ 有四种新的情况：
\(\begin{cases} f_{i+1}=x_a\\ g_{i+1}=y_b\\ \end{cases} \begin{cases} f_{i+1}=x_{a+1}\\ g_{i+1}=y_b\\ \end{cases} \begin{cases} f_{i+1}=x_a\\ g_{i+1}=y_{b+1}\\ \end{cases} \begin{cases} f_{i+1}=x_{a+1}\\ g_{i+1}=y_{b+1}\\ \end{cases}\) 相当于从状态 $(a,b)$ 转移到 $(a+1,b),(a,b+1),(a+1,b+1)$。
原问题相当于一个 $n\times m$ 的网格，钦定 $f_i<g_i$，则有 $(i,j)$ 染为黑色当且仅当 $x_i<y_j$。求从 $(1,1)$ 能否走到 $(n,m)$。其余节点染为白色。
因此可以设计 $\textit{dp}_{i,j}$ 表示从 $(1,1)$ 能否走到 $(i,j)$。
-
若 $x_1<y_1$，有： \(\textit{dp}_{i,j}=(\textit{dp}_{i-1,j}\lor\textit{dp}_{i,j-1})\land[x_i<y_j]\)
-
否则若 $x_1>y_1$，有：
\[\textit{dp}_{i,j}=(\textit{dp}_{i-1,j}\lor\textit{dp}_{i,j-1})\land[x_i>y_j]\] -
当 $x_1=y_1$时无解，需要特判。
因此得到了一个 $\mathcal O(nm)$ 的 DP，总时间复杂度 $\mathcal O(qnm)$。
期望得分：$\text{35pts}$。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=2000,M=2000;
int n,m,x[N+1],y[M+1];
bool check(){
if(n==1&&m==1&&x[1]==y[1]){
return false;
}
static bool dp[N+1][M+1];
memset(dp,0,sizeof(dp));
dp[1][1]=true;
if(x[1]<y[1]){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]|=(dp[i-1][j]||dp[i][j-1])&&(x[i]<y[j]);
}
}
}else if(x[1]>y[1]){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]|=(dp[i-1][j]||dp[i][j-1])&&(x[i]>y[j]);
}
}
}
return dp[n][m];
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int c,q;
cin>>n>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>x[i];
}
for(int i=1;i<=m;i++){
cin>>y[i];
}
cout<<check();
while(q--){
vector<pair<int,int> >kx,ky;
int sizeX,sizeY;
cin>>sizeX>>sizeY;
kx.resize(sizeX);ky.resize(sizeY);
#define p first
#define v second
for(auto &i:kx){
cin>>i.p>>i.v;
}
for(auto &i:ky){
cin>>i.p>>i.v;
}
for(auto &i:kx){
swap(x[i.p],i.v);
}
for(auto &i:ky){
swap(y[i.p],i.v);
}
cout<<check();
for(auto &i:kx){
x[i.p]=i.v;
}
for(auto &i:ky){
y[i.p]=i.v;
}
#undef p
#undef v
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# 测试点 $8\sim20$
钦定 $f_i<g_i$。
有解不好考虑，考虑什么情况无解。
无解仅有四种情况：
1. 一行全部为白色，即 $\max\limits_{i=1}^nx_i\geq\max\limits_{i=1}^my_i$。
2. 一列全部为白色，即 $\min\limits_{i=1}^nx_i\geq\min\limits_{i=1}^my_i$。
3. 起点被一个「L 形白色图形」包围，即存在 $(i,j)$，满足 $x_i\geq\max\limits_{k=1}^jy_k\land \min\limits_{k=1}^ix_k\geq y_j$。
4. 终点被一个「L 形白色图形」包围，即存在 $(i,j)$，满足 $x_i\geq\max\limits_{k=j}^my_k\land\min\limits_{k=i}^nx_k\geq y_j$。
第 $1,2$ 两种情况都可以线性求解。
第 $3,4$ 两种情况对称，将 $x,y$ 翻转后即可将第 $4$ 种情况转化为第 $3$ 种。考虑如何高效判断第 $3$ 种情况。
发现所有**有效的** $x_i$ 一定是**单调递增**的。因此，只考虑这些有效的 $x_i$。
不满足条件，即 $\max\limits_{k=1}^jy_k>x_i$，因此**有效的** $y_j$ 也**单调递增**。只考虑有效的 $y_j$。
维护指针 $j$ 为满足 $\max\limits_{k=1}^jy_k>x_i$ 的**最小的** $j$，指针 $k$ 为满足 $y_k\leq\min\limits_{l=1}^ix_l$ 的**最小的** $k$。若 $k<j$，则代表**满足第 $3$ 种情况**。
# AC 代码
```cpp
//#include<bits/stdc++.h>
#include
-
using namespace std;
constexpr const int N=5e5,M=5e5;
int n,m,x[N+1],y[M+1];
bool check(int x[],int n,int y[],int m){
if(x[1]>=y[1]){
return false;
}
int maxX=x[1],maxY=y[1],minX=x[1],minY=y[1];
for(int i=1;i<=n;i++){
maxX=max(maxX,x[i]);
minX=min(minX,x[i]);
}
for(int i=1;i<=m;i++){
maxY=max(maxY,y[i]);
minY=min(minY,y[i]);
}
if(maxX>=maxY||minX>=minY){
return false;
}
int j=1;
for(int i=1,preMinX=x[1],j=1,k=1;i<=n;i++){
preMinX=min(preMinX,x[i]);
while(j<=m&&y[j]<=x[i]){
j++;
}
while(k<j&&preMinX<y[k]){
k++;
}
if(k<j){
return false;
}
}
reverse(x+1,x+n+1);
reverse(y+1,y+m+1);
j=1;
for(int i=1,preMinX=x[1],j=1,k=1;i<=n;i++){
preMinX=min(preMinX,x[i]);
while(j<=m&&y[j]<=x[i]){
j++;
}
while(k<j&&preMinX<y[k]){
k++;
}
if(k<j){
reverse(x+1,x+n+1);
reverse(y+1,y+m+1);
return false;
}
}
reverse(x+1,x+n+1);
reverse(y+1,y+m+1);
return true;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int c,q;
cin>>n>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>x[i];
}
for(int i=1;i<=m;i++){
cin>>y[i];
}
cout<<(check(x,n,y,m)||check(y,m,x,n));
while(q--){
vector<pair<int,int> >kx,ky;
int sizeX,sizeY;
cin>>sizeX>>sizeY;
kx.resize(sizeX);ky.resize(sizeY);
#define p first
#define v second
for(auto &i:kx){
cin>>i.p>>i.v;
}
for(auto &i:ky){
cin>>i.p>>i.v;
}
for(auto &i:kx){
swap(x[i.p],i.v);
}
for(auto &i:ky){
swap(y[i.p],i.v);
}
cout<<(check(x,n,y,m)||check(y,m,x,n));
for(auto &i:kx){
x[i.p]=i.v;
}
for(auto &i:ky){
y[i.p]=i.v;
}
#undef p
#undef v
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
