BOJ 16074 Mountaineers

출처 : https://www.acmicpc.net/problem/16074

각 cell에 1, 2, 3, 4, ,,, (h * w)번호를 매긴 후 이 새로 인덱싱한 번호는 노드 번호로 취급

이후 각 인접한 노드(상, 하, 좌, 우)와 연결(엣지)을 하는게 두 노드 간의 cost는 누 도느 중 max값이 두 노드 사이의 cost가 됨. 이렇게 만들어진 그래프에서 MST를 구성한 뒤 LCA를 통해 두 노드 사이의 최대값을 구하면 이 값이 쿼리의 답이 됨. 만약 두 노드가 같다면 (같은 cell) 그 cell에 적혀있는 값이 답이 됨.

#include<stdio.h>
#include<malloc.h>
struct edge
{
	int a, b, c, f;
};
struct edge list[1000000], sorted[1000000];
int h, w, qn, map[500][500], en, vn;
int dx[4] = { -1, 1 ,0 ,0 };
int dy[4] = { 0, 0, -1, 1 };
int up[250001], ur[250001];
int* elist[250001], eindex[250001];
int size[250001], pa[250001], cn[250001], cd[250001], ci[250001], cidx[250001], dnum[250001], num;
int n, node, s, e, l, r, g, * tree;
void input();
void ex_e();
int isin(int, int);
int get_max(int, int);
int get_node_num(int, int);
void save(int, int, int);
void make_mst();
void msort(struct edge[], int, int);
void merge(struct edge[], int, int, int);
int find(int);
void uni(int, int);
void lnk(int, int);
void pb(int, int);
void build_hld();
int go1(int, int);
void go2(int, int, int, int);
void build_seg();
void seg_update(int, int);
int seg_query(int, int, int, int, int);
void proc();
int change(int, int);
int query(int, int);
int lca(int, int);
int hq(int, int);
void fin();
int main(void)
{
	input();
	ex_e();
	make_mst();
	build_hld();
	build_seg();
	proc();
	fin();
	return 0;
}
void input()
{
	int i, j;
	scanf("%d %d %d", &h, &w, &qn);
	for (i = 0, vn = h * w; i < h; i++)
	{
		for (j = 0; j < w; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
}
void ex_e()
{
	int i, j, d, nx, ny, cost, a, b;
	for (i = 0, a = 1; i < h; i++)
	{
		for (j = 0; j < w; j++)
		{
			for (d = 0; d < 4; d++)
			{
				nx = i + dx[d];
				ny = j + dy[d];
				if (isin(nx, ny))
				{
					cost = get_max(map[i][j], map[nx][ny]);
					b = get_node_num(a, d);
					save(a, b, cost);
				}
			}
			up[a] = a;
			a++;
		}
	}
}
int isin(int x, int y)
{
	return 0 <= x && x < h && 0 <= y && y < w;
}
int get_max(int a, int b)
{
	return a > b ? a : b;
}
int get_node_num(int c, int d)
{
	switch (d)
	{
	case 0:
		return c - w;
	case 1:
		return c + w;
	case 2:
		return c - 1;
	case 3:
		return c + 1;
	}
}
void save(int a, int b, int c)
{
	list[en].a = a;
	list[en].b = b;
	list[en].c = c;
	list[en++].f = 0;
}
void make_mst()
{
	int i, c;
	msort(list, 0, en - 1);
	for (i = c = 0; i < en; i++)
	{
		if (find(list[i].a) != find(list[i].b))
		{
			c++;
			list[i].f = 1;
			uni(list[i].a, list[i].b);
			pb(list[i].a, list[i].b);
			pb(list[i].b, list[i].a);
		}
	}
}
void msort(struct edge list[], int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) >> 1;
		msort(list, left, mid);
		msort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}
void merge(struct edge list[], int left, int mid, int right)
{
	int i, j, k, l;
	i = k = left;
	j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (list[i].c < list[j].c)
		{
			sorted[k++] = list[i++];
		}
		else
		{
			sorted[k++] = list[j++];
		}
	}
	if (mid < i)
	{
		for (l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else
	{
		for (l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}
	for (l = left; l <= right; l++)
	{
		list[l] = sorted[l];
	}
}
int find(int x)
{
	if (x == up[x])
	{
		return x;
	}
	return up[x] = find(up[x]);
}
void uni(int x, int y)
{
	lnk(find(x), find(y));
}
void lnk(int x, int y)
{
	if (ur[x] > ur[y])
	{
		up[y] = x;
	}
	else
	{
		up[x] = y;
		if (ur[x] == ur[y])
		{
			ur[y]++;
		}
	}
}
void pb(int a, int b)
{
	elist[a] = (int*)realloc(elist[a], sizeof(int) * (eindex[a] + 1));
	elist[a][eindex[a]++] = b;
}
void build_hld()
{
	go1(1, 0);
	go2(1, 0, 1, 0);
}
int go1(int c, int p)
{
	int d, next;
	size[c] = 1;
	pa[c] = p;
	for (d = 0; d < eindex[c]; d++)
	{
		next = elist[c][d];
		if (next != p)
		{
			size[c] += go1(next, c);
		}
	}
	return size[c];
}
void go2(int c, int p, int ccn, int ccd)
{
	int d, next, h;
	dnum[c] = ++num;
	cn[c] = ccn;
	cd[c] = ccd;
	ci[c] = cidx[ccn]++;
	for (d = 0, h = -1; d < eindex[c]; d++)
	{
		next = elist[c][d];
		if (next != p && (h == -1 || size[next] > size[h]))
		{
			h = next;
		}
	}
	if (h != -1)
	{
		go2(h, c, ccn, ccd);
	}
	for (d = 0; d < eindex[c]; d++)
	{
		next = elist[c][d];
		if (next != p && next != h)
		{
			go2(next, c, next, ccd + 1);
		}
	}
}
void build_seg()
{
	int i;
	for (node = s = l = r = 1; r - l + 1 < vn; l <<= 1, r <<= 1, r |= 1);
	for (tree = (int*)calloc(r + 1, sizeof(int)), e = r - l + 1, g = l - 1, i = 0; i < en; i++)
	{
		if (list[i].f)
		{
			seg_update(g + (pa[list[i].a] == list[i].b ? dnum[list[i].a] : dnum[list[i].b]), list[i].c);
		}
	}
}
void seg_update(int idx, int val)
{
	tree[idx] = val;
	idx >>= 1;
	while (idx)
	{
		tree[idx] = get_max(tree[idx << 1], tree[idx << 1 | 1]);
		idx >>= 1;
	}
}
int seg_query(int node, int start, int end, int left, int right)
{
	int mid;
	if (left > end || right < start)
	{
		return 0;
	}
	if (left <= start && end <= right)
	{
		return tree[node];
	}
	mid = (start + end) >> 1;
	return get_max(seg_query(node << 1, start, mid, left, right), seg_query(node << 1 | 1, mid + 1, end, left, right));
}
void proc()
{
	int x1, y1, x2, y2;
	while (qn--)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		printf("%d\n", query(change(x1, y1), change(x2, y2)));
	}
}
int change(int x, int y)
{
	return (x - 1) * w + y;
}
int query(int a, int b)
{
	int l, x, y;
	if (a == b)
	{
		if (!(a % w))
		{
			x = (a / w);
			y = w;
		}
		else
		{
			x = (a / w) + 1;
			y = a % w;
		}
		return map[x - 1][y - 1];
	}
	l = lca(a, b);
	return get_max(hq(l, a), hq(l, b));
}
int lca(int a, int b)
{
	while (cn[a] != cn[b])
	{
		if (cd[a] > cd[b])
		{
			a = pa[cn[a]];
		}
		else
		{
			b = pa[cn[b]];
		}
	}
	return ci[a] > ci[b] ? b : a;
}
int hq(int a, int b)
{
	int ans = -1;
	while (cn[a] != cn[b])
	{
		ans = get_max(ans, seg_query(node, s, e, dnum[cn[b]], dnum[b]));
		b = pa[cn[b]];
	}
	return get_max(ans, seg_query(node, s, e, dnum[a] + 1, dnum[b]));
}
void fin()
{
	int i;
	for (free(tree), i = 0; i <= vn; i++)
	{
		if (elist[i])
		{
			free(elist[i]);
		}
	}
}