原题链接
OK呀，也是先悄咪咪的偷看一眼这道题的标签好吧，ok，动态规划+贪心，还有一个不认识的Ad-hoc，管那么多干嘛，分析题意开始
原问题相当于给定一个二分图，上点 i 和下点 j 可以连边当且仅当 xi>yj。求是否可以每个点至少连一条边且所有边不交（重边视为相交）。发现如果存在边(i,j) 和边 (i+1,j+1)，一定可以存在边 (i,j+1) 或(i+1,j)。这是好证的，xi>yj,xi+1>yj+1，假设不存在边 (i,j+1) 即 xi≤yj+1，则xi+1>yj+1≥xi>yj 即存在边 (i+1,j)。
由此，我们需要为这个二分图连 n+m−1 条不交的边，每个点至少连了一条边。由于我们钦定 fi>gi，所以特殊性质为 xn 是唯一最大值ym 是唯一最小值。
若 Y 中存在元素不小于 xn，显然无解，同理 X 中存在元素不大于 ym 也无解。
显然最后一定存在一条边 (n,m)，考虑其它一定存在的边。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=505050,inf=1e9+7;
inline int read(){int x=0;char ch=getchar();for(;!('0'<=ch&&ch<='9');ch=getchar());for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x;
}
int a[N],b[N],c[N],d[N],pa[N],pb[N],oa[N],ob[N];
inline int clac(int *a,int*b,int n,int m){if(a[1]<=b[1])return 0;a[n+1]=inf;b[m+1]=-inf;int w=inf,p=1;f(i,1,n){for(w=min(w,a[i]);b[p]>=w;)++p;pa[i]=p;}w=-inf;p=1;f(i,1,m){for(w=max(w,b[i]);a[p]<=w;)++p;pb[i]=p;}while(n>1&&m>1){if(pa[n]<m){m=pa[n];continue;}if(pb[m]<n){n=pb[m];continue;}return 0;}return 1;
}
inline int doing(int*a,int*b,int n,int m){a[0]=-inf;b[0]=inf;int pa=0,pb=0;f(i,1,n)if(a[i]>a[pa])pa=i;f(i,1,m)if(b[i]<b[pb])pb=i;f(i,1,n)if(a[i]<=b[pb])return 0;f(i,1,m)if(b[i]>=a[pa])return 0; int na=0,nb=0;f(i,1,pa)c[++na]=a[i];f(i,1,pb)d[++nb]=b[i];if(!clac(c,d,na,nb))return 0;na=nb=0;g(i,n,pa)c[++na]=a[i];g(i,m,pb)d[++nb]=b[i];if(!clac(c,d,na,nb))return 0;return 1;
}
signed main(){int c,q,ka,kb;c=read();n=read();m=read();q=read();f(i,1,n)oa[i]=read(); f(i,1,m)ob[i]=read();f(_,0,q){f(i,1,n)a[i]=oa[i];f(i,1,m)b[i]=ob[i];if(_){ka=read();kb=read();f(e,1,ka)c=read(),a[c]=read();f(e,1,kb)c=read(),b[c]=read();}if(a[1]>b[1])putchar(doing(a,b,n,m)^48);else putchar(doing(b,a,m,n)^48);}return 0;
}参考博客：P9870 [NOIP2023] 双序列拓展 - 洛谷专栏 (luogu.com.cn)