有八个数组 x/y 的 前/后 缀最 大/小 的位置。

其命名方法为:

第一个字母表示前后缀，前缀为 p,后缀为 l.

第二个字母表示最大最小，最大为 a，最小为i。

第三个字母表示关于x还是y。

#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int c,n,m,q;
int x[500100],y[500100];
int xx[500100],yy[500100];
int pix[500100],pax[500100],piy[500100],pay[500100],lix[500100],lax[500100],liy[500100],lay[500100];
void update(int x[],int y[],int n,int m){
	for(int i=1;i<=n;i++){
		if(i==1)pix[i]=pax[i]=1;
		else{
			if(x[i]<x[pix[i-1]])pix[i]=i;
			else pix[i]=pix[i-1];
			if(x[i]>x[pax[i-1]])pax[i]=i;
			else pax[i]=pax[i-1];			
		}
	}
	for(int i=n;i>0;i--){
		if(i==n)lix[i]=lax[i]=i;
		else{
			if(x[i]<x[lix[i+1]])lix[i]=i;
			else lix[i]=lix[i+1];
			if(x[i]>x[lax[i+1]])lax[i]=i;
			else lax[i]=lax[i+1];			
		}
	}
	for(int i=1;i<=m;i++){
		if(i==1)piy[i]=pay[i]=1;
		else{
			if(y[i]<y[piy[i-1]])piy[i]=i;
			else piy[i]=piy[i-1];
			if(y[i]>y[pay[i-1]])pay[i]=i;
			else pay[i]=pay[i-1];			
		}
	}
	for(int i=m;i>0;i--){
		if(i==m)liy[i]=lay[i]=i;
		else{
			if(y[i]<y[liy[i+1]])liy[i]=i;
			else liy[i]=liy[i+1];
			if(y[i]>y[lay[i+1]])lay[i]=i;
			else lay[i]=lay[i+1];			
		}
	}
}
bool check1(int i,int j,int x[],int y[],int n,int m){
	if(i==1||j==1)return 1;
	if(x[pix[i-1]]<y[piy[j-1]])return check1(pix[i-1],j,x,y,n,m);
	if(x[pax[i-1]]<y[pay[j-1]])return check1(i,pay[j-1],x,y,n,m);
	return 0;
}
bool check2(int i,int j,int x[],int y[],int n,int m){
	if(i==n||j==m)return 1;
	if(x[lix[i+1]]<y[liy[j+1]])return check2(lix[i+1],j,x,y,n,m);
	if(x[lax[i+1]]<y[lay[j+1]])return check2(i,lay[j+1],x,y,n,m);
	return 0;
}
bool solve(int x[],int y[],int n,int m){
	if(x[1]>=y[1])return 0;
	update(x,y,n,m);
//	cerr << pix[n] << " " << piy[m] << " " << pax[n] << " " << pay[m] << endl;
//	cerr << x[pix[n]] << " " << y[piy[m]] << " " << x[pax[n]] << " " << y[pay[m]] << endl;
	if(x[pix[n]]>=y[piy[m]]||x[pax[n]]>=y[pay[m]])return 0;
	return check1(pix[n],pax[m],x,y,n,m)&&check2(pix[n],pax[m],x,y,n,m);
}
int kx,ky,p,v;
signed main(){
//#ifndef LOCAL
//	freopen("expand.in","r",stdin);
//	freopen("expand.out","w",stdout);
//#endif
	R(c);R(n);R(m);R(q);
	for(int i=1;i<=n;i++)R(x[i]);
	for(int i=1;i<=m;i++)R(y[i]);
	write(solve(x,y,n,m)||solve(y,x,m,n));
	while(q--){
		for(int i=1;i<=n;i++)xx[i]=x[i];
		for(int i=1;i<=m;i++)yy[i]=y[i];
		R(kx);R(ky);
		while(kx--){
			R(p);R(v);
			xx[p]=v;
		}
		while(ky--){
			R(p);R(v);
			yy[p]=v;
		}
		write(solve(xx,yy,n,m)||solve(yy,xx,m,n));
	}
    return 0;
}