悬赏2个关注

#include<iostream>
#include<climits>
#define int long long
using namespace std;
const int N = 1e5 + 100;
int n, m, q, a[N], b[N];
int a1[N];
struct Segment_Tree_A {
	int T[N << 2];
	void push_up(int p, int flag) {
		if(flag == 0) T[p] = max(T[p << 1], T[p << 1 | 1]);
		else if(flag == 1) T[p] = min(T[p << 1], T[p << 1 | 1]);
	}
	void build(int p, int l, int r, int flag) {
		if(l == r) {
			T[p] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1, l, mid, flag);
		build(p << 1 | 1, mid + 1, r, flag);
		push_up(p, flag);
	}
	int query(int ql, int qr, int p, int l, int r, int flag) {
		if(ql <= l && r <= qr) return T[p];
		int mid = (l + r) >> 1, ans;
		if(flag == 0) ans = LLONG_MIN;
		else if(flag == 1) ans = LLONG_MAX;
		if(flag == 0) {
			if(ql <= mid) ans = max(ans, query(ql, qr, p << 1, l, mid, 0));
			if(qr > mid) ans = max(ans, query(ql, qr, p << 1 | 1, mid + 1, r, 0));
		}
		else if(flag == 1) {
			if(ql <= mid) ans = min(ans, query(ql, qr, p << 1, l, mid, 1));
			if(qr > mid) ans = min(ans, query(ql, qr, p << 1 | 1, mid + 1, r, 1));
		}
		return ans;
	}
} Amax, Amin, Amax1, Amin1;
struct Segment_Tree_B {
	int T[N << 2];
	void push_up(int p, int flag) {
		if(flag == 0) T[p] = max(T[p << 1], T[p << 1 | 1]);
		else if(flag == 1) T[p] = min(T[p << 1], T[p << 1 | 1]);
	}
	void build(int p, int l, int r, int flag) {
		if(l == r) {
			T[p] = b[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1, l, mid, flag);
		build(p << 1 | 1, mid + 1, r, flag);
		push_up(p, flag);
	}
	int query(int ql, int qr, int p, int l, int r, int flag) {
		if(ql <= l && r <= qr) return T[p];
		int mid = (l + r) >> 1, ans;
		if(flag == 0) ans = LLONG_MIN;
		else if(flag == 1) ans = LLONG_MAX;
		if(flag == 0) {
			if(ql <= mid) ans = max(ans, query(ql, qr, p << 1, l, mid, 0));
			if(qr > mid) ans = max(ans, query(ql, qr, p << 1 | 1, mid + 1, r, 0));
		}
		else if(flag == 1) {
			if(ql <= mid) ans = min(ans, query(ql, qr, p << 1, l, mid, 1));
			if(qr > mid) ans = min(ans, query(ql, qr, p << 1 | 1, mid + 1, r, 1));
		}
		return ans;
	}
} Bmax, Bmin;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; ++ i) {
		cin >> a[i];
		a1[i] = a[i];
	}
	for(int i = 1; i <= m; ++ i) cin >> b[i];
	Amax.build(1, 1, n, 0);
	Amin.build(1, 1, n, 1);
	Bmax.build(1, 1, n, 0);
	Bmin.build(1, 1, n, 1);
	for(int i = 1; i <= n; ++ i)
		if(a[i] >= 0) a[i] = LLONG_MIN;
	Amax1.build(1, 1, n, 0);
	for(int i = 1; i <= n; ++ i) a[i] = a1[i];
	for(int i = 1; i <= n; ++ i)
		if(a[i] < 0) a[i] = LLONG_MAX;
	Amin1.build(1, 1, n, 1);
	while(q --) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		int t1 = Amax.query(l1, r1, 1, 1, n, 0);
		int t2 = Amin.query(l1, r1, 1, 1, n, 1);
		int t3 = Bmax.query(l2, r2, 1, 1, n, 0);
		int t4 = Bmin.query(l2, r2, 1, 1, n, 1);
		int t5 = Amax1.query(l1, r1, 1, 1, n, 0);
		int t6 = Amin1.query(l1, r1, 1, 1, n, 1);
		int ans = LLONG_MIN;
		if(t1 < 0) {
			if(t3 < 0) ans = t2 * t3;
			else ans = t1 * t3;
		}
		else if(t2 >= 0) {
			if(t4 >= 0) ans = t1 * t4;
			else ans = t2 * t4;
		}
		else {
			if(t3 < 0) ans = t2 * t3;
			else if(t4 >= 0) ans = t1 * t4;
			else ans = max(t6 * t4, t5 * t3);
		}
		/*
		if(t1 >= 0) ans = max(ans, t1 * t4);
		if(t1 < 0) ans = max(ans, t1 * t3);
		if(t2 >= 0) ans = max(ans, t2 * t4);
		if(t2 < 0) ans = max(ans, t2 * t3);
		ans = max(ans, t6 * t4);
		ans = max(ans, t5 * t3);
		*/
		cout << ans << "\n";
	}
	return 0;
}

代码已经AC

我的代码采用了这里的贪心方法，

但我想知道为什么第一种贪心（即我的代码的注释部分）是不正确的

球球了