백준 25112 / C++

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

25112번: Single-track railway

 

[ 풀이 ] 

매번 업데이트하면서 min(S[n]-2*S[i])를 찾아주는 문제이다. 

펜윅트리로 업데이트해주고, S[i]<S[n]/2 를 찾는건 이분탐색으로 해주자. 주의할 점은 

i를 찾은 후 S[n]-S[i]와 S[n]-S[i+1] 중 작은 걸 리턴해주면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 200002;
ll n, m, t[MAX], a, b, tree[MAX];

void upd(int i, int v) {
	while (i < MAX) tree[i] += v, i += i & -i;
}

ll sum(int i) {
	ll ret = 0;
	while (i) ret += tree[i], i -= i & -i;
	return ret;
}

ll solve() {
	int l = 1, r = n;
	int i = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (2 * sum(mid) <= sum(n)) {
			i = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return min(abs(sum(n) - 2 * sum(i)), abs(sum(n) - 2 * sum(i + 1)));
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		cin >> t[i]; upd(i, t[i]);
	}
	cin >> m;
	cout << solve() << '\n';
	while (m--) {
		cin >> a >> b;
		upd(a, b - t[a]);
		t[a] = b;
		cout << solve() << '\n';
	}
}