打败了100%用户

毕生，加入银光蒙蒙的刷题小分队获取更多题解

让我们瞟一眼代码：

#include<bits/stdc++.h>
#define N 500005

using namespace std;
int c, n, m, Q;
int X[N], Y[N];
struct node {
	int id, val;
}A_pre_max[N], A_pre_min[N], A_suf_max[N], A_suf_min[N], B_pre_max[N], B_pre_min[N], B_suf_max[N], B_suf_min[N];
node add1(node x, node y) {
	node z;
	z.val = min(x.val, y.val);
	if(z.val == x.val) z.id = x.id;
	else z.id = y.id;
	return z;
}
node add2(node x, node y) {
	node z;
	z.val = max(x.val, y.val);
	if(z.val == x.val) z.id = x.id;
	else z.id = y.id;
	return z;
}
bool check1(int x, int y) { //判断[1,1]是否能走到第x行或第y列 
	if(x == 1 || y == 1) return 1;
	node xmin = A_pre_min[x - 1], xmax = A_pre_max[x - 1];
	node ymin = B_pre_min[y - 1], ymax = B_pre_max[y - 1];
	if(xmin.val < ymin.val) return check1(xmin.id, y);
	if(xmax.val < ymax.val) return check1(x, ymax.id);
	return 0;
}
bool check2(int x, int y, int n, int m) { //目前能走到第x行和第y列,判断其是否能走到[n,m] 
	if(x == n || y == m) return 1;
	node xmin = A_suf_min[x + 1], xmax = A_suf_max[x + 1];
	node ymin = B_suf_min[y + 1], ymax = B_suf_max[y + 1];
	if(xmin.val < ymin.val) return check2(xmin.id, y, n, m);
	if(xmax.val < ymax.val) return check2(x, ymax.id, n, m);
	return 0;
}
bool Sol(int n, int m, int X[], int Y[]) {
	if(X[1] > Y[1]) return 0;
	A_pre_max[1] = A_pre_min[1] = ((node){1, X[1]});
	B_pre_max[1] = B_pre_min[1] = ((node){1, Y[1]});
	A_suf_max[n] = A_suf_min[n] = ((node){n, X[n]});
	B_suf_max[m] = B_suf_min[m] = ((node){m, Y[m]});
	for(int i = 2; i <= n; i++) {
		A_pre_min[i] = add1(A_pre_min[i - 1], (node){i, X[i]});
		A_pre_max[i] = add2(A_pre_max[i - 1], (node){i, X[i]});
	}
	for(int i = n - 1; i >= 1; i--) {
		A_suf_min[i] = add1(A_suf_min[i + 1], (node){i, X[i]});
		A_suf_max[i] = add2(A_suf_max[i + 1], (node){i, X[i]});
	}
	for(int i = 2; i <= m; i++) {
		B_pre_min[i] = add1(B_pre_min[i - 1], (node){i, Y[i]});
		B_pre_max[i] = add2(B_pre_max[i - 1], (node){i, Y[i]});
	}
	for(int i = m - 1; i >= 1; i--) {
		B_suf_min[i] = add1(B_suf_min[i + 1], (node){i, Y[i]});
		B_suf_max[i] = add2(B_suf_max[i + 1], (node){i, Y[i]});
	}
	if(A_pre_min[n].val >= B_pre_min[m].val || A_pre_max[n].val >= B_pre_max[m].val) return 0;
	return check1(A_pre_min[n].id, B_pre_max[m].id) && check2(A_pre_min[n].id, B_pre_max[m].id, n, m);
}
int AA[N], BB[N];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> c >> n >> m >> Q;
	for(int i = 1; i <= n; i++) cin >> X[i], AA[i] = X[i];
	for(int i = 1; i <= m; i++) cin >> Y[i], BB[i] = Y[i];
	cout << (Sol(n, m, X, Y) || Sol(m, n, Y, X));
	while(Q--) {
		int kx, ky;
		cin >> kx >> ky;
		for(int i = 1; i <= n; i++) X[i] = AA[i];
		for(int i = 1; i <= m; i++) Y[i] = BB[i];
		for(int i = 1, p, v; i <= kx; i++) {
			cin >> p >> v;
			X[p] = v;
		}
		for(int i = 1, p, v; i <= ky; i++) {
			cin >> p >> v;
			Y[p] = v;
		}
		cout << (Sol(n, m, X, Y) || Sol(m, n, Y, X));
	}
	return 0;
}

毕生，这个代码是不是非常的短？
不要直接复制啊
有更好的方法可以评论
（这里用了预处理 + 贪心递归 + 双向验证的方法，如果有疑惑可以打在评论区）