t = int(input())
for T in range(t):
	la, lb = map(int, input().split())
	ra, rb = map(int, input().split())
	if la > lb:
		la, lb, ra, rb = lb, la, rb, ra
	if la < lb and rb < ra:
		print("NO")
	else:
		print("YES")

#include <bits/stdc++.h>
 
using namespace std;
 
void solve(){
	long long x, y, k;
	cin >> x >> y >> k;
	while (k > 0 && x != 1) {
		long long ost = (x / y + 1) * y - x;
        ost = max(1ll, ost);
        ost = min(ost, k);
        x += ost;
		while (x % y == 0) {
			x /= y;
		}
		k -= ost;
	}
	cout << x + k % (y - 1) << '\n';
}
 
int main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Все числа $$$a_{i}$$$ положительные, может ли это как то помочь?

Попробуйте воспользоваться динамическим программированием.

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1000000007;
 
void solve(){
	int n, l, r;
	cin >> n >> l >> r;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
 
	vector<long long> pref(n + 1);
	for (int i = 0; i < n; i++){
		pref[i + 1] = pref[i] + a[i];
	}
 
	vector<int> dp(n + 1);
	int s = 0;
	int j = -1;
	for (int i = 0; i < n; i++){
		dp[i + 1] = max(dp[i + 1], dp[i]);
		if (j < i){
			j = i;
			s = 0;
		}
		while(j < n && s < l){
			s += a[j++];
		}
		if (s >= l && s <= r){
			dp[j] = max(dp[j], dp[i] + 1);
		}
		s -= a[i];
	}
 
	cout << dp[n] << '\n';
}
 
int main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

t = int(input())
for T in range(t):
	n, l, r = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	cur = 0
	L, R = 0, 0
	while L < n:
		while R < n and cur < l:
			cur += a[R]
			R += 1
		if l <= cur and cur <= r:
			ans += 1
			L = R
			cur = 0
		else:
			cur -= a[L]
			L += 1
	print(ans)

Как изменяется разница между высотами, если мы выберем конкретную подматрицу?

Стоит свести задачу к математической конструкции. Может что-то из теории чисел может помочь?

import math
 
def solve():
    n, m, k = map(int, input().split())
    a = [[int(x) for x in input().split()] for j in range(n)]
    s = [input() for i in range(n)]
    pref = [[0 for i in range(m + 1)] for j in range(n + 1)]
    diff = 0
    for i in range(n):
        cur = 0
        for j in range(m):
            if s[i][j] == '1':
                cur += 1
                diff += a[i][j]
            else:
                diff -= a[i][j]
            pref[i + 1][j + 1] = pref[i][j + 1] + cur
    if diff == 0:
        print("YES")
        return
    g = 0
    for i in range(n - k + 1):
        for j in range(m - k + 1):
            f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j]
            f = abs(k * k - 2 * f)
            g = math.gcd(g, f)
    if g == 0 or diff % g != 0:
        print("NO")
    else:
        print("YES")
 
 
if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

Попробуйте использовать подход "разделяй и властвуй".

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 1000000007;
 
map<pair<long long, int>, tuple<int, long long, long long>> mem;
 
tuple<int, long long, long long> calc(long long n, int k){
	if (k < 0){
		return tuple{0, 0ll, 0ll};
	}
	if (n == 1){
		return tuple{1, 1ll, 1ll};
	}
	int bit = 63 - __builtin_clzll(n);
	long long mid = (1ll << bit);
	if (mid == n){
		mid >>= 1;
		if (mem.count({n, k})){
			return mem[{n, k}];
		}
	}
	auto [f1, s1, e1] = calc(mid, k);
	auto [f2, s2, e2] = calc(n - mid, k - 1);
 
	int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD;
	f1 = (f1 * 1ll - sub1 + MOD) % MOD;
	int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD;
	f2 = (f2 * 1ll - sub2 + MOD) % MOD;
 
	long long p = (e1 + s2) % MOD;
	int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD;
	long long s_cur = s1;
	long long e_cur = e2;
	if (s1 == e1 && s1 != 0){
		s_cur = (s1 + s2);
	}
	if (s2 == e2 && s2 != 0){
		e_cur = (e1 + e2);
	}
	if ((mid << 1) == n){
		mem[{n, k}] = tuple{f_cur, s_cur, e_cur};
	}
	return tuple{f_cur, s_cur, e_cur};
};
 
void solve(){
	long long n;
	int k;
	cin >> n >> k;
	cout << get<0>(calc(n, k)) << '\n';
}
 
int main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Если поддерживать множество таких индексов $$$i$$$, что $$$a_{i} < a_{i - 1}$$$, то может ли это как то помочь?

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1000000007;
 
struct SegTree{
	vector<int> mn, mx;
	int n;
	SegTree(int _n): n(_n){
		mx.assign(2 * n, -inf);
		mn.resize(2 * n, inf);
	}
 
	void upd(int pos, int val){
		mx[pos + n] = val;
		mn[pos + n] = val;
		pos = (pos + n) >> 1;
		for (;pos > 0; pos >>= 1){
			mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]);
			mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]);
		}
	}
 
	pair<int,int> get(int l, int r){
		pair<int,int> res = {-inf, inf};
		l += n;
		r += n + 1;
		for (;l < r; l >>= 1, r >>= 1){
			if (l & 1) {
				res.first = max(res.first, mx[l]);
				res.second = min(res.second, mn[l++]);
			}
			if (r & 1) {
				res.first = max(res.first, mx[--r]);
				res.second = min(res.second, mn[r]);
			}			
		}
		return res;
	}
};
 
void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
 
	SegTree tree(n);
	set<int> st;
	for (int i = 0; i < n; i++){
		tree.upd(i, a[i]);
		if (i > 0 && a[i] < a[i - 1]){
			st.insert(i);
		}
	}
 
	function<int(int, int)> find_pref = [&](int pos, int x){
		if (pos < 0){
			return 0;
		}
		int l = 0, r = pos;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (a[m] > x){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		return r + 1;
	};
 
	function<int(int, int)> find_suff = [&](int pos, int x){
		if (pos >= n){
			return n - 1;
		}
		int l = pos, r = n - 1;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (a[m] >= x){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		return r;
	};
 
	function<void()> query = [&](){
		if (st.empty()){
			cout << -1 << ' ' << -1 << '\n';
			return;
		}
		int l = *st.begin() - 1;
		int r = *(--st.end());
 
		auto [mx, mn] = tree.get(l, r);
 
		cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n';
	};
 
	query();
	int q;
	cin >> q;
	for (int i = 0; i < q; i++){
		int pos, val;
		cin >> pos >> val;
		pos--;
		if (pos > 0 && a[pos] < a[pos - 1]){
			st.erase(pos);
		}
		if (pos + 1 < n && a[pos + 1] < a[pos]){
			st.erase(pos + 1);
		}
		a[pos] = val;
		tree.upd(pos, val);
		if (pos > 0 && a[pos] < a[pos - 1]){
			st.insert(pos);
		}
		if (pos + 1 < n && a[pos + 1] < a[pos]){
			st.insert(pos + 1);
		}
		query();
	}
}
 
int main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}