这是代码，复杂度应该是对的，常数太大了，求大佬卡卡常

#include <bits/stdc++.h>

using namespace std;
const int N = 5e5+5; 
int c, n, m, q, a[N], b[N], p[N][2], v[N][2], maxn[N], minn[N], tt[N]; 

bool solve (int a[], int n, int b[], int m) {
    if (a[1] <= b[1] || a[n] <= b[m]) return 0; 
    maxn[n] = n; minn[n] = n; 
    for (int i = n-1;i >= 1;i--) { 
        maxn[i] = maxn[i+1]; minn[i] = minn[i+1]; 
        if (a[i] > a[maxn[i]]) maxn[i] = i; 
        if (a[i] < a[minn[i]]) minn[i] = i; 
    } 
    int l = 1, r = 1, t = 1, z = 1; tt[m] = m; 
    for (int i = m-1;i >= 1;i--) {
        tt[i] = tt[i+1]; 
        if (b[i] < b[tt[i]]) tt[i] = i; 
    } 
    while (t <= n) {
        int g = maxn[t], gm = minn[g]; 
        for (int i = t;i <= g;i++) {
            while (r < m && a[i] > b[r+1]) r++; 
            while (l <= m && a[i] <= b[l]) l++; 
            if (l > r) return 0; 
        }
        if (r < m) return 0; 
        while (z < m && b[tt[z+1]] < a[gm]) z++; 
        if (z < l) return 0; 
        l = r = z; 
        t = gm+1; 
    } 
    return 1;
}

int main () {
//    freopen("expand.in", "r", stdin); 
//    freopen("expand.out", "w", stdout); 
	scanf("%d%d%d%d", &c, &n, &m, &q); 
	for (int i = 1;i <= n;i++) scanf("%d", &a[i]); 
	for (int i = 1;i <= m;i++) scanf("%d", &b[i]); 
	int t = 1; 
	int ans = solve(a, n, b, m)|solve(b, m, a, n); 
	printf("%d", ans); 
	while (q--) {
		int k1, k2; scanf("%d%d", &k1, &k2); 
		for (int i = 1;i <= k1;i++) {
			scanf("%d%d", &p[i][0], &v[i][0]); swap(v[i][0], a[p[i][0]]); 
		}
		for (int i = 1;i <= k2;i++) {
			scanf("%d%d", &p[i][1], &v[i][1]); swap(v[i][1], b[p[i][1]]); 
		}
		ans = solve(a, n, b, m)|solve(b, m, a, n); 
		printf("%d", ans); 
		for (int i = 1;i <= k1;i++) a[p[i][0]] = v[i][0];  
		for (int i = 1;i <= k2;i++) b[p[i][1]] = v[i][1]; 
	}
	return 0;
}