[BOJ/C++] shake! 2021 E ~ I번 (BOJ 24232, 24233, 24234, 24235, 24236)

오랜만의 포스팅입니다.

하던 일에 진전이 별로 없었기 때문에 포스팅할 것도 없네요.

이번엔 2021 shake의 나머지 문제를 모두 풀어봤습니다.

억까 때문에 스트레스가 쌓여서 PS는 이제 그만 건드릴까 생각 중입니다.

 

이전 문제들 (A ~ D번)은 여기에서 확인하실 수 있습니다.

 

BOJ 24232. 망가진 나무

문제 링크 : https://www.acmicpc.net/problem/24232

24232번: 망가진 나무

풀이 : 2021 shake의 E번, F번, G번, I번 모두 공식 풀이 슬라이드를 한 번씩은 참고한 것 같습니다.

이번 문제는 주어진 방향 그래프를 어떤 정점을 기준으로 다른 모든 정점에 도달할 수 있게 (다른 모든 정점으로 뻗어나가는 모양새가 되도록) 하기 위한 간선 변경 횟수의 최솟값을 구해야 합니다.

일단 어떤 정점을 기준으로 그래프 탐색을 한 뒤에, 그 그래프에서 다른 정점마다 체크해주면 됩니다.

귀찮아서 마우스로 대충 그렸다

위 그림에서처럼, 정점 $A$를 기준으로 한 번 구한 뒤에는, 정점 $B$ 사이의 간선을 뒤집어주는 것으로 정점 B를 기준으로 구할 수 있게 됩니다. 이렇게 두 개 종류의 그래프 탐색을 돌리면 되고, 여기서 저는 답을 구하기 위해 최소 비용을 가지는 정점에 대해 그래프 탐색을 다시 한 번 더 돌려서 정답 문자열을 구했습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

struct edge
{
	int node;
	bool dir;
	int idx;
	edge(int n, bool d, int i) : node(n), dir(d), idx(i) {};
};

int N, u, v, d[100001], M = 101010, Mi;
vector<edge> graph[100001];
bool visited[100001];
string ans;

int dfs1(int cur)
{
	visited[cur] = 1;

	int ret = 0;
	for (auto& p : graph[cur])
		if (!visited[p.node]) ret += dfs1(p.node) + p.dir;
	return ret;
}

void dfs2(int from, int to, bool dir)
{
	visited[to] = 1;
	if (dir) d[to] = d[from] - 1;
	else d[to] = d[from] + 1;

	for (auto& p : graph[to])
		if (!visited[p.node]) dfs2(to, p.node, p.dir);
}

void dfs3(int cur)
{
	visited[cur] = 1;
	for (auto& p : graph[cur])
		if (!visited[p.node])
		{
			ans[p.idx] = p.dir + '0';
			dfs3(p.node);
		}
}

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

	cin >> N;
	ans.resize(N - 1);

	for (int i = 1; i < N; i++)
	{
		cin >> u >> v;
		graph[u].emplace_back(v, 0, i - 1);
		graph[v].emplace_back(u, 1, i - 1);
	}

	d[1] = dfs1(1);

	memset(visited, 0, sizeof(visited));
	visited[1] = 1;
	for (auto& p : graph[1])
		dfs2(1, p.node, p.dir);

	for (int i = 1; i <= N; i++)
		if (M > d[i])
		{
			M = d[i];
			Mi = i;
		}

	memset(visited, 0, sizeof(visited));
	dfs3(Mi);

	cout << ans;
	return 0;
}

 

BOJ 24233. 낚시

문제 링크 : https://www.acmicpc.net/problem/24233 

24233번: 낚시

풀이 : F번부터는 좀 많이 헤맸습니다. 풀이만으로는 잘 와닿지 않은 것도 있고, 이해를 잘 못한 것도 있었기 때문입니다. 그게 꼴받아서 여기서라도 풀이 쓰고 코드 올리는 거죠

 

어느 시점 $t$에 물고기를 가장 많이 낚을 수 있는 위치 $x$는, 물고기부터가 구간으로 나타나기 때문에 위치도 구간으로 나타납니다. 따라서 어느 한 지점으로 조정해줄 필요가 있습니다. 간편하게 물고기의 시작 지점으로 둡시다. (공식 풀이에도 나오지만 끝 지점으로 둘 수도 있고, 이 경우에는 조정을 반대 방향으로 해주어야 합니다)

 

어떤 물고기의 시작 지점 $x$에서 낚는 물고기 수는 다른 물고기가 $x$에 진입하기 시작할 때 +1, 완전히 구간 밖으로 벗어났을 때 -1이 됩니다. 따라서 각 물고기마다 물고기의 시작 지점을 기준으로 다른 물고기의 진입, 퇴장 시간대를 구한 뒤 정렬하여 +1, -1을 해주면서 최대 갯수를 구해주면 됩니다. 동일 시간대에서는 진입을 퇴장보다 우선 순위에 둡니다.

 

이러고 나서 몇 번 틀리고 막혔던 것이, $i$번째 물고기의 시작 지점을 기준으로 한다면 이 $i$번째 물고기 또한 움직일 수 있기 때문에 이를 고려해야 한다는 점입니다. 저는 처음에 단순히 0초대의 시작 지점을 parameter로 주고 계산해서 기준 물고기가 움직이지 않게 되는 오류를 범했습니다. 이 상태에서 시간 $t$를 구하려고 하니 시간 초과는 둘째치고 구할 방법부터가 없어서 헤맸습니다.

 

따라서 시간에 따른 $i$번째 물고기의 위치 또한 반영하면서 다른 물고기의 진입/퇴장 시간을 구해줄 필요가 있습니다.

pair<double, double> getTime(int i, int j)
{
    double s = (double)(f[i].S - f[j].S) / (f[j].V - f[i].V);
    double e = (double)(f[i].S - f[j].E) / (f[j].V - f[i].V);
    
    return { min(s, e), max(s, e) };
}

등식 $S_i + V_i \times t = S_j + V_j \times t$를 $t$에 대해 풀면 됩니다.

$i$번째 물고기의 시작 지점을 기준으로 하기 때문에, $j$번째 물고기의 퇴장 시간은 $S_i + V_i \times t = E_j + V_j \times t$ 를 풀어야 합니다.

 

각 물고기의 이동 방향이 어떻게 될지 모르므로, 시작 지점이 먼저 만날지 끝 지점이 먼저 만날지 모릅니다. 따라서 min, max로 다시 판별해주어야 합니다. 또한 이렇게 구한 시간은 음수일 수 있으니 추후에 처리해야 합니다.

 

위 pseudo 코드에는 고려되지 않았지만, 두 물고기의 이동 속도가 같은 경우에는 divisor가 0이 되는 문제가 있습니다.

이 경우에는 두 물고기가 처음부터 구간이 겹치지 않는 한 만나지 않으므로, 이 조건을 체크해서 따로 예외처리 해줄 필요가 있습니다.

 

이렇게 구한 시간을 정렬하여 물고기 수를 세어주면 됩니다. 작살을 던지는 시간 $t \ge 0$이므로 시간이 0 이상일 때만 최대값을 구해줘야 합니다. 이를 각 물고기마다 돌려서 $O(N^2 log N)$에 답을 구할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<double, double> p;
typedef pair<double, int> p2;

struct fish
{
	int S, E, V;

	fish(int s = 0, int e = 0, int v = 0) : S(s), E(e), V(v) {}

	p getTime(fish& f)
	{
		if (V == f.V)
		{
			if (S <= f.S && f.S <= E) return { 1, 1 };
			else return { -1, -1 };
		}

		double s = (double)(f.S - S) / (V - f.V);
		double e = (double)(f.S - E) / (V - f.V);

		return { min(s, e), max(s, e) };
	}
};

bool compare(p2& a, p2& b)
{
	if (a.first != b.first) return a.first < b.first;
	else return a.second > b.second;
}

int N, ans = 1;
fish f[1001];
vector<p2> tm;

int solve(int idx)
{
	tm.clear();

	for (int j = 0; j < N; j++)
	{
		if (idx == j) continue;
		p t = f[j].getTime(f[idx]);

		if (f[idx].V == f[j].V)
		{
			if (t.first > 0) tm.emplace_back(0, 1);
			else continue;
		}
		else
		{
			tm.emplace_back(t.first, 1);
			tm.emplace_back(t.second, -1);
		}
	}

	sort(tm.begin(), tm.end(), compare);
	int cur = 1, ret = 1;

	for (auto& t : tm)
	{
		cur += t.second;
		if (t.first >= 0) ret = max(ret, cur);
	}

	return ret;
}

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

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> f[i].S >> f[i].E >> f[i].V;

	for (int i = 0; i < N; i++)
		ans = max(ans, solve(i));

	cout << ans;
	return 0;
}

 

BOJ 24234. 1차원 체스

문제 링크 : https://www.acmicpc.net/problem/24234

24234번: 1차원 체스

풀이 : 딱 보면 Trie 겠거니 할 수 있습니다. 실제로 푸는 데는 시간이 좀 걸렸지만 말입니다.

$K - 1$번째 기보까지는 같고, $K$번째 기보에서 다른 값이 나와야하기 때문에

1 2 3 4 와 1 2 3 6은 기점 3을 갖지만, 1 2 3 4 와 1 2 3 4 6은 기점을 갖지 않습니다. (첫 번째 기보에 $K = 5$번째 기보 값이 존재하지 않습니다)

 

Trie를 구성하고 보면, 어떤 노드가 기점이 되는 경우의 수는 그 노드의 서브트리마다 존재하는 기보의 수를 $S$라고 했을 때, $S$가 이룰 수 있는 모든 쌍의 곱을 합한 것과 같습니다.

(예를 들어 어떤 노드의 $j$번째 서브트리의 기보 수를 $S_j$라고 한다면, 경우의 수는 $S_1 S_2 + S_1 S_3 + ...$가 됩니다.)

이를 각각마다 구해서 합해주기엔 시간 초과가 발생하므로, $(a+b+c+..)^2 = (a^2 + b^2 + c^2 + ...) + 2 (ab + ac + ...)$를 이용하여 [서브트리의 각 $S$의 제곱 합 - 서브트리의 각 $S$의 합의 제곱] / 2를 구해줍시다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long ll;

unordered_map<int, ll> ans;

struct Trie
{
	unordered_map<int, Trie*> next;
	int S, val;
	int finish;

	Trie() : S(0), finish(0), val(-1)
	{
	}

	~Trie()
	{
		for (auto& p : next)
			delete p.second;
	}

	void insert(vector<int>& v, int key)
	{
		if (key >= v.size())
		{
			finish++;
			return;
		}

		if (next.find(v[key]) == next.end())
		{
			next[v[key]] = new Trie;
			next[v[key]]->val = v[key];
		}

		next[v[key]]->insert(v, key + 1);
	}

	int solve()
	{
		S = 0;
		ll cnt = 0, sq = 0;
		for (auto& p : next)
		{
			cnt = p.second->solve();
			S += cnt;
			sq += cnt * cnt;
		}

		ans[val] += ((ll)S * S - sq) / 2;
		return S += finish;
	}
};

Trie trie;
int N, Q, S, a;
vector<int> A;

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

	cin >> N >> Q;
	for (int i = 0; i < N; i++)
	{
		cin >> S;
		A.clear();
		for (int j = 0; j < S; j++)
		{
			cin >> a;
			A.push_back(a);
		}

		trie.insert(A, 0);
	}

	trie.solve();
	
	while (Q--)
	{
		cin >> a;
		cout << ans[a] << '\n';
	}
	return 0;
}

 

BOJ 24235. 유산

문제 링크 : https://www.acmicpc.net/problem/24235

24235번: 유산

풀이 : 이거 하나를 못 풀어서 100트를 한 사람이 있다????

문제는 생각보다 간단합니다. 주어진 깃발 지점에 대해서 convex hull을 구한 뒤에 다각형의 넓이로 이분 탐색을 해주면 됩니다. 직선 $x = a$로 잘리는 지점은 convex hull의 edge와 교점을 구해서 처리해주면 됩니다.

다각형의 넓이는 ccw를 이용해 구할 수 있으니 찾아보시기 바랍니다.

 

그런데 안 풀렸습니다. 왜?

일단 시간 초과가 발생합니다. $R - L > 10^{-3}$으로 다시 시도해보진 않았습니다만 $10^{-4}$가 시간 초과가 났으니 Time Limit가 굉장히 빡빡하다는 것을 알 수 있었습니다.

그래서 그냥 50번 정도 반복하는 것으로 바꿨습니다. 대충 이 정도 이상은 돌려야 적당히 넘어가는 것을 확인했습니다.

 

그러고는 틀렸습니다. 왜???????????????

이걸 해결을 못해서 몇십트를 박았는데도 안 풀렸습니다. 지금은 풀었으니 이렇게 쓰지만 말입니다.

assert를 다시 몇 번 박아서야 ccw 값이 음수가 나온다는 것을 확인했습니다.

graham scan으로 반시계 정렬을 이미 했고, 그렇기 때문에 0 이상의 값이 나와야하는 데 말입니다.

절댓값으로 바꿔서 돌려도 15% 대에서 틀렸습니다가 나왔기 때문에 이분 탐색 이전에 문제가 발생한다는 사실은 명확했습니다.

 

그래서 다른 다각형의 넓이 문제 풀이를 봤는데 (예를 들어 1077번), 반시계 정렬 방법이 다른 것 아니겠습니까?

이건 억까입니다 억울해요 가장 대표적인 문제인 2166번은 그걸로 풀렸단 말입니다.

정렬 방법을 바꾸고 돌렸더니, 풀렸네요? 이렇게 거한 삽질은 처음이었습니다.

 

정리하면, 도대체 무슨 희한한 예외 케이스가 있는지는 몰라도 기준점을 min_element로 구하고 0번째와 단순히 swap하는 것으로는 완벽하게 반시계 정렬을 할 수가 없습니다. 전체에 대해 좌표값 기준 정렬을 한 번 수행한 뒤에, 1번째 부터 마지막까지 (0번째는 자연스레 최소점이 될 것이고) 반시계 정렬을 돌려야 합니다.

 

이렇게 푸니까 2초 limit에 1800ms대가 나왔습니다. 1차원 체스도 그렇고 리미트가 좀 많이 빡빡하네요.

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>

using namespace std;

typedef pair<double, double> p;

p pivot;

double ccwd(p a, p b, p c)
{
	double val = a.first * b.second + b.first * c.second + c.first * a.second - a.second * b.first - b.second * c.first - c.second * a.first;
	return val;
}

bool cmp(p& A, p& B)
{
	if (A.first == B.first)
		return A.second < B.second;
	else
		return A.first < B.first;
}

bool compare(p& A, p& B)
{
	double c = ccwd(pivot, A, B);
	if (c == 0) return cmp(A, B);

	return c > 0;
}

void graham(vector<p>& v, vector<p>& hull)
{
	sort(v.begin(), v.end(), cmp);
	pivot = v[0];
	sort(v.begin() + 1, v.end(), compare);

	for (auto& i : v)
	{
		while (hull.size() >= 2 && ccwd(hull[hull.size() - 2], hull[hull.size() - 1], i) <= 0)
			hull.pop_back();

		hull.push_back(i);
	}
}

double getArea(vector<p>& hull, double x)
{
	double ret = 0;
	int S = hull.size();
	p pt, pt2;
	bool ch1 = 0;

	for (int i = 1; i < S; i++)
	{
		if (hull[i].first > x)
		{
			if (!ch1)
			{
				double grad = hull[i].second - hull[i - 1].second;
				grad /= hull[i].first - hull[i - 1].first;
				pt.first = x;
				pt.second = hull[i - 1].second + grad * (x - hull[i - 1].first);

				ret += ccwd(pivot, hull[i - 1], pt);
				ch1 = 1;
			}
			continue;
		}

		if (ch1)
		{
			double grad = hull[i].second - hull[i - 1].second;
			grad /= hull[i].first - hull[i - 1].first;
			pt2.first = x;
			pt2.second = hull[i - 1].second + grad * (x - hull[i - 1].first);

			ret += ccwd(pivot, pt, pt2) + ccwd(pivot, pt2, hull[i]);
			ch1 = 0;
			continue;
		}
		ret += ccwd(pivot, hull[i - 1], hull[i]);
	}

	if (ch1)
	{
		double grad = hull[0].second - hull[S - 1].second;
		grad /= hull[0].first - hull[S - 1].first;
		pt2.first = x;
		pt2.second = hull[S - 1].second + grad * (x - hull[S - 1].first);
		double val = ccwd(pivot, pt, pt2);
		ret += val;
	}

	return ret;
}

int L = 2e9, R = -2e9;
double binary(vector<p>& hull)
{
	pivot = hull[0];

	double mid = 0;
	int S = hull.size();

	double area = 0, temp = 0;
	for (int i = 1; i < S; i++)
	{
		double val = ccwd(pivot, hull[i - 1], hull[i]);
		area += val;
	}

	area = area * 0.5;

	while (L + 1 < R)
	{
		mid = (L + R) / 2;
		temp = getArea(hull, mid);

		if (temp > area) R = mid;
		else if (temp < area) L = mid;
		else break;
	}

	double LL = L, RR = R;
	for (int i = 0; i < 16; i++)
	{
		mid = (LL + RR) / 2;
		temp = getArea(hull, mid);

		if (temp > area) RR = mid;
		else if (temp < area) LL = mid;
	}

	return (LL + RR) * 0.5;
}

int N, x, y;
vector<p> v, hull;

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

	cout << fixed << setprecision(6);
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		v.emplace_back(x, y);
		L = min(L, x);
		R = max(R, x);
	}

	graham(v, hull);

	cout << binary(hull);
	return 0;
}

코드를 보면 아시겠지만 굉장히 너저분합니다. 특히 이분 탐색에서 시간을 어떻게든 줄여보려고 이런 저런 짓을 많이 해놨군요.

 

BOJ 24236. 1차원 애니팡

문제 링크 : https://www.acmicpc.net/problem/24236

24236번: 1차원 애니팡

풀이 : 주어진 수열에 대해 모든 인접한 수의 부호가 다르도록 변경하는 최소 비용을 구해야 합니다.

ex) 1 0 0 1 -> 1 0 -1 1

T번 수열 값이 변경되고, 이는 쿼리라고 볼 수 있겠습니다.

쿼리하면 세그먼트 트리죠. 위 수열을 세그먼트 트리에 끼워넣어 봅시다.

-1을 곱하는 비용이 $R$, +1 또는 -1을 하는 비용이 $C$이고 이는 위치와 상관 없습니다.

따라서 인접한 수의 부호가 다른 두 수열을 합친다면 왼쪽 수열의 오른쪽 값, 오른쪽 수열의 왼쪽 값만 조건을 만족하도록 신경쓰면 되겠네요. 이를 계산하기 위해서 수열의 맨 왼쪽 값 부호와 맨 오른쪽 값 부호에 따라 비용을 계산하겠습니다.

각 값이 가질 수 있는 부호는 3개 (-, 0, +)이므로 가능한 경우의 수는 9개입니다.

각 경우에 대해 그 부호가 가능한 경우인지, 가능하다면 비용은 얼마나 되는지를 계산하면 됩니다.

점화식으로 표현한다면, 두 수열을 합친 수열의 맨 왼쪽 값의 부호가 $i$, 맨 오른쪽 값의 부호가 $j$일때

($l$은 왼쪽 수열의 최소 비용, $r$은 오른쪽 수열의 최소 비용이며, 여기서 -는 0, 0은 1, +는 2로 표현하겠습니다.)

$V[i][j] = \min_{0 \le k < 3} (l[i][k] + \min (r[(k + 1) \% 3][j], r[(k + 2) \% 3][j]))$ 라고 할 수 있습니다.

 

불가능한 경우는 최댓값으로 미리 만들어두고 업데이트하면 됩니다. 아마 $10^9$ 이상의 값이면 되지 않을까 싶네요.

근데 수열의 길이가 하나인 경우에는 조금 처리가 다릅니다.

먼저 왼쪽 값과 오른쪽 값의 부호가 같아야만 합니다. ($0 \le i < 3, i \neq j$에 대해 $V[i][i] = 0, V[i][j] = MAX$)

그리고 각 부호에 따라 비용 또한 달라집니다.

$A_i = 0$인 경우 $V[0][0] = V[2][2] = C, V[1][1] = 0$

$A_i < 0$인 경우 $V[0][0] = 0, V[1][1] = -A_i \times C, V[2][2] = \min(R, (-A_i + 1) \times C)$

$A_i > 0$인 경우 $V[0][0] = \min(R, (A_i + 1) \times C), V[1][1] = A_i \times C, V[2][2] = 0$

 

수열 값 업데이트는 초기화와 비슷하게 처리해주면 되고,

최소 비용은 최상단 노드의 $V[i][j]$ 중 최솟값을 반환하면 됩니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int N, R, C, T;

const ll MAX = 1e15;

struct Node
{
	int left, right;
	ll val[3][3]; //- 0 +
};

struct segTree
{
	Node v[1 << 18];

	void init(int* input, int index, int rangeStart, int rangeEnd)
	{
		if (rangeStart == rangeEnd)
		{
			v[index].left = v[index].right = input[rangeStart];
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
					v[index].val[i][j] = MAX;

			if (input[rangeStart] == 0)
			{
				v[index].val[0][0] = v[index].val[2][2] = C;
				v[index].val[1][1] = 0;
			}
			else
			{
				v[index].val[0][0] = input[rangeStart] < 0 ? 0 : min((input[rangeStart] + 1) * C, R);
				v[index].val[1][1] = abs(input[rangeStart]) * C;
				v[index].val[2][2] = input[rangeStart] > 0 ? 0 : min((-input[rangeStart] + 1) * C, R);
			}
			return;
		}

		int mid = (rangeStart + rangeEnd) >> 1;

		init(input, index << 1, rangeStart, mid);
		init(input, index << 1 | 1, mid + 1, rangeEnd);

		v[index].left = v[index << 1].left;
		v[index].right = v[index << 1 | 1].right;

		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
			{
				v[index].val[i][j] = MAX;
				for (int k = 0; k < 3; k++)
					v[index].val[i][j] = min(v[index].val[i][j], v[index << 1].val[i][k] + min(v[index << 1 | 1].val[(k + 1) % 3][j], v[index << 1 | 1].val[(k + 2) % 3][j]));
			}

		return;
	}

	void update(int nodeIndex, int rangeStart, int rangeEnd, int index, int val)
	{
		if (index < rangeStart || index > rangeEnd) return;

		if (rangeStart != rangeEnd)
		{
			int mid = (rangeStart + rangeEnd) >> 1;
			update(nodeIndex << 1, rangeStart, mid, index, val);
			update(nodeIndex << 1 | 1, mid + 1, rangeEnd, index, val);

			v[nodeIndex].left = v[nodeIndex << 1].left;
			v[nodeIndex].right = v[nodeIndex << 1 | 1].right;

			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
				{
					v[nodeIndex].val[i][j] = MAX;
					for (int k = 0; k < 3; k++)
						v[nodeIndex].val[i][j] = min(v[nodeIndex].val[i][j], v[nodeIndex << 1].val[i][k] + min(v[nodeIndex << 1 | 1].val[(k + 1) % 3][j], v[nodeIndex << 1 | 1].val[(k + 2) % 3][j]));
				}
		}
		else
		{
			v[nodeIndex].left = v[nodeIndex].right = val;
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
					v[nodeIndex].val[i][j] = MAX;

			if (val == 0)
			{
				v[nodeIndex].val[0][0] = v[nodeIndex].val[2][2] = C;
				v[nodeIndex].val[1][1] = 0;
			}
			else
			{
				v[nodeIndex].val[0][0] = val < 0 ? 0 : min((val + 1) * C, R);
				v[nodeIndex].val[1][1] = abs(val) * C;
				v[nodeIndex].val[2][2] = val > 0 ? 0 : min((-val + 1) * C, R);
			}
		}
	}

	ll query()
	{
		ll ret = MAX;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				ret = min(ret, v[1].val[i][j]);
		return ret;
	}
};

segTree tree;
int input[101010], K, V;

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

	cin >> N >> R >> C >> T;
	
	for (int i = 0; i < N; i++) cin >> input[i];
	tree.init(input, 1, 0, N - 1);
	cout << tree.query() << '\n';

	while (T--)
	{
		cin >> K >> V;
		tree.update(1, 0, N - 1, K - 1, V);
		cout << tree.query() << '\n';
	}

	return 0;
}

 

그래도 어찌어찌 다 풀었습니다.

이제 다시 할 일 하러 가야겠네요.

앞에서도 말했듯이 PS는 한동안 안 건드릴 것 같습니다. 또 뭔가 잘 풀었다 싶은 게 있으면 포스팅을 올리겠습니다.