취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13557번 문제인 수열과 쿼리 10이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13557 

각 구간마다 (가능한 구간의 구간합의 최댓값), (왼쪽 끝을 포함하는 가능한 구간의 구간합의 최댓값), (오른쪽 끝을 포함하는 가능한 구간의 구간합의 최댓값), (구간합) 네가지 정보를 관리하는 세그먼트트리를 구현해 문제를 해결하자.

구간합이 최대인 구간의 구간합이 음수가 되는 경우의 처리에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

struct node {
	ll val, lval, rval, tval;
	node() {};
	node(ll val, ll lval, ll rval, ll tval) {
		this->val = val, this->lval = lval, this->rval = rval, this->tval = tval;
	}
};

int N, Q;
ll arr[100001];
node seg[262145];

void init(int L, int R, int sI) {
	node& nodeC = seg[sI];
	if (L == R) {
		ll& tmp = arr[L];
		if (tmp < 0) nodeC = node(0, 0, 0, tmp);
		else nodeC = node(tmp, tmp, tmp, tmp);
	}
	else {
		init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1);
		node& nodeL = seg[sI * 2], & nodeR = seg[sI * 2 + 1];
		nodeC.val = max(nodeL.rval + nodeR.lval, max(nodeL.val, nodeR.val));
		nodeC.tval = nodeL.tval + nodeR.tval;
		nodeC.lval = max(nodeL.lval, nodeL.tval + nodeR.lval);
		nodeC.rval = max(nodeR.rval, nodeR.tval + nodeL.rval);
	}
}

node valquery(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return node(0, 0, 0, 0);;
	if (qL <= L && R <= qR) return seg[sI];
	node nodeL = valquery(L, (L + R) / 2, qL, qR, sI * 2), nodeR = valquery((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
	ll retL = max(nodeL.lval, nodeL.tval + nodeR.lval);
	ll retR = max(nodeR.rval, nodeR.tval + nodeL.rval);
	ll retT = nodeL.tval + nodeR.tval;
	ll retV = max(nodeL.rval + nodeR.lval, max(nodeL.val, nodeR.val));
	return node(retV, retL, retR, retT);
}

ll maxseg[262145];
ll init2(int L, int R, int sI) {
	if (L == R) return maxseg[sI] = arr[L];
	return maxseg[sI] = max(init2(L, (L + R) / 2, sI * 2), init2((L + R) / 2 + 1, R, sI * 2 + 1));
}

ll rangemax(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return -1000000007LL;
	if (qL <= L && R <= qR) return maxseg[sI];
	return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	init(1, N, 1);
	init2(1, N, 1);

	cin >> Q;
	while (Q--) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

		if (y1 < x2) {
			ll val1 = valquery(1, N, x1, y1 - 1, 1).rval, val2 = valquery(1, N, y1, x2, 1).tval, val3 = valquery(1, N, x2 + 1, y2, 1).lval;
			cout << val1 + val2 + val3 << '\n';
		}
		else {
			ll	val1 = valquery(1, N, x2, y1, 1).val,
				val2 = valquery(1, N, x1, x2 - 1, 1).rval + arr[x2] + valquery(1, N, x2 + 1, y2, 1).lval,
				val3 = valquery(1, N, x1, y1 - 1, 1).rval + arr[y1] + valquery(1, N, y1 + 1, y2, 1).lval;
			if (val1 <= 0 && val2 <= 0 && val3 <= 0) {
				ll lrval = valquery(1, N, x1, x2 - 1, 1).rval, rlval = valquery(1, N, y1 + 1, y2, 1).lval;
				cout << max(max(rangemax(1, N, x2, y1, 1), lrval + valquery(1, N, x2, y1, 1).tval + rlval), max(lrval + arr[x2], arr[y1] + rlval)) << '\n';
			}
			else cout << max(val1, max(val2, val3)) << '\n';
		}
	}
}