突然发现本题的一个非 Ad-hoc 套路做法。

首先如果 $x_1\le y_1$ 那么拓展后只有 $y$ 全大于 $x$ 是有可能的，反之亦然。这里我们只考虑 $x_1 > y_1$，并尝试在拓展后使得 $x$ 全大于 $y$。

把 $x$，$y$ 序列差分，然后视为你当前有一个 HP 为 $x$ 对应位置的值减 $y$ 对应位置的值，且你的 HP 始终不能小于等于 $0$，也就是你初始有 $x_1-y_1$ 点 HP，把 $x_{i-1}$ 拓展到 $x_i$ 会获得 $x_i-x_{i-1}$ 点 HP（如果值为负则改为消耗绝对值点 HP），对于 $y$ 序列类似操作。

问题转化为：给定一棵树（形态为根节点下面挂着一条长度为 $n-1$ 的链和一条长度为 $m-1$ 的链），除根节点外每个点有一只怪兽，打败它需要先消耗 $a_i$ 点 HP，再恢复 $b_i$ 点 HP，求初始拥有给定量 HP 的情况下从根节点出发按照最优策略能否打败所有怪兽。

发现这个问题严格弱于 HDU 6326 Monster Hunter，直接按照那题的做法做即可，类似的题还有 P7011 [CERC2013] Escape、QOJ 7520 Monster Generator。

具体地，$a\le b$ 的显然比 $a>b$ 的优，然后同样 $a\le b$ 的显然 $a$ 越小越优。考虑把问题倒过来看，那么 $a>b$ 的倒过来看就变成了 $a\le b$ 的情况了，所以 $b$ 越大越优。

然后考虑一个节点，如果其子节点比它优，那么选它之后肯定还会选那个子节点，那就合并它和它的子节点，最后直接贪即可，树上的话还得注意一下合并子节点的顺序，以及用堆维护贪心，时间复杂度单 $\log$。

但这个题只需要类似链表维护合并，然后直接二路归并即可，时间复杂度 $O(q(n+m))$。

还有一个问题，本题中两个序列可以同时推进一格。但考虑如果两个都是“减少 HP”或者“增加 HP”的事件的话是等价的，如果两个不同的话，先进行“增加”事件再进行“减少”事件一定不劣于同时进行，所以可以直接做。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct node{int a,b;}x[N],y[N];
inline bool operator < (node &x,node &y){
	if((x.a<=x.b)&&(y.a>y.b))return 0;
	if((y.a<=y.b)&&(x.a>x.b))return 1;
	if(x.a<=x.b)return(x.a>y.a);
	return(x.b<y.b);
}
inline node operator + (node x,node y){
	node res;
	res.a=max(x.a,x.a-x.b+y.a),res.b=x.b+y.b-x.a-y.a+res.a;
	return res;
}
int c,n,m,q,a[N],b[N],r[N],kx,ky,ta[N],tb[N];
bool solve(int a[],int n,int b[],int m){
	if(a[1]<=b[1])return 0;
	node res={0,a[1]-b[1]};
	for(int i=2;i<=n;i++){
		int t=a[i]-a[i-1];
		if(t>=0)x[i]={0,t};
		else x[i]={-t,0};
	}
	for(int i=2;i<=m;i++){
		int t=b[i]-b[i-1];
		if(t>=0)y[i]={t,0};
		else y[i]={0,-t};
	}
	iota(r+1,r+n,2),r[n]=0;
	for(int i=n-1;i;i--)while(r[i]&&(x[i]<x[r[i]]))x[i]=x[i]+x[r[i]],x[r[i]]={0,0},r[i]=r[r[i]];
	iota(r+1,r+m,2),r[m]=0;
	for(int i=m-1;i;i--)while(r[i]&&(y[i]<y[r[i]]))y[i]=y[i]+y[r[i]],y[r[i]]={0,0},r[i]=r[r[i]];
	int tx=1,ty=1;
	while((tx<=n)||(ty<=m)){
		if(ty>m)res=res+x[tx++];
		else if(tx>n)res=res+y[ty++];
		else{
			if(y[ty]<x[tx])res=res+x[tx++];
			else res=res+y[ty++];
		}
	}
	return(!res.a)&&(res.b>0);
}
inline void work(){
	if(solve(a,n,b,m)||solve(b,m,a,n))cout<<1;
	else cout<<0;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>c>>n>>m>>q;
	for(int i=1;i<=n;i++)cin>>a[i],ta[i]=a[i];
	for(int i=1;i<=m;i++)cin>>b[i],tb[i]=b[i];
	work();
	while(q--){
		cin>>kx>>ky,memcpy(a,ta,sizeof(ta)),memcpy(b,tb,sizeof(tb));
		for(int i=1,p,d;i<=kx;i++)cin>>p>>d,a[p]=d;
		for(int i=1,p,d;i<=ky;i++)cin>>p>>d,b[p]=d;
		work();
	}
	return 0;
}