Boj 10167) 금광

문제

백준 10167

설명

연속합과 쿼리 의 아이디어가 그대로 쓰이는 문제. 이 아이디어는 이 문제의 이름을 본따 금광쿼리로 한국에선 많이 부른다고 한다.

가능한 Y축 범위의 모든 경우의 수가 O(\(\mathrm{N}^2\)) 인데, X축도 가능한 모든 범위의 경우를 고려하면 시간초과가 나는 것이 뻔하다. 하지만 Y축의 범위를 고정했을 때, X축의 범위는 모든 경우를 고려할 필요가 없다. 대신 선택한 Y축 범위에 포함되는 금광들에 대해서 X축을 기준으로 최대 연속합을 구하면 된다. 이를 세그트리로 풀게되면 X축에 대해선 시간복잡도가 로그단위가 되어 제한시간 내에 풀 수 있게 된다.

비슷한 쉬운버전 문제를 먼저 풀고 오긴 했지만, 처음으로 내 힘으로 푼 다이아 문제라 감회가 깊다.

시간 복잡도

O(\(\mathrm{N}^2 \log{\mathrm{N}}\))

코드

using ll = long long;

template<typename T, size_t _H>
class SegmentTree
{
public:
	struct Node {
		Node() {}
		Node(T v) : acc(v), total_m(v), lm(v), rm(v) { }
		Node operator+(const Node& in)
		{
			Node res;

			res.acc = acc + in.acc;
			res.lm = max(lm, acc + in.lm);
			res.rm = max(in.rm, in.acc + rm);
			res.total_m = max(rm + in.lm, max(total_m, in.total_m));
	
			return res;
		}
	
		T total_m = -1e15, lm = -1e15, rm = -1e15, acc = 0;
	};
	
	void Update(int i, const T& v) {
		for (i += INDEX_MAX - 1, nodes[i] = v, i >>= 1; i >= 1; i >>= 1)
			nodes[i] = nodes[i << 1] + nodes[(i << 1)+1];
	}
	
	Node nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
};

vector<int> xs, ys;
inline int GetXI(int x) { return upper_bound(xs.begin(), xs.end(), x) - xs.begin(); }
inline int GetYI(int y) { return upper_bound(ys.begin(), ys.end(), y) - ys.begin(); }

struct P { int x, y, w; } inputs[3001];
struct II { int x, w; };
vector<II> board[3001];

SegmentTree<ll, 13> seg;

int main()
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		xs.push_back(x); ys.push_back(y);
		inputs[i] = { x, y, w };
	}
	
	// 좌표 압축
	sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	for (int i = 1; i <= n; i++)
		board[GetYI(inputs[i].y)].push_back({ GetXI(inputs[i].x), inputs[i].w });
	
	ll ans = -1e15;
	
	// Y 축 범위의 시작지점
	for (int i = 1; i <= ys.size(); i++)
	{
	    // 시작점이 초기화 되었으므로 세그트리도 초기화한다.
		fill(seg.nodes, seg.nodes + (1 << 13), SegmentTree<ll, 13>::Node());
		
		// Y 축 범위의 끝지점
		for (int j = i; j <= ys.size(); j++)
		{
		    // Y 가 j 인 모든 금광을 세그트리에 더한다. 
			for (auto p : board[j])		
				seg.Update(p.x, seg.nodes[p.x + seg.INDEX_MAX - 1].acc + p.w);	
	         
	        // Y 가 (i ~ j) 범위인 금광에 대해서 X 축 기준 최대 연속합을 구해 최댓값을 갱신한다.
			ans = max(ans, seg.nodes[1].total_m);
		}
	}
	cout << ans;
}