Lorenzo Von Matterhorn [Codeforces 362 : Div2 C, Div1 A]

問題

http://codeforces.com/contest/697/problem/C

要素数が無限の完全二分木がある。
根から近い順に1から番号がついている。
最初、全ての辺のコストは0である。
この時、クエリ1またはクエリ2を q 個処理する。

クエリ1
頂点 u から頂点 v への最短経路で使われる辺のコストを w だけ増やす

クエリ2
頂点 u から頂点 v への最短距離で使われる辺のコストの総和を答える

1 <= q <= 10^3
1 <= v, w <= 10^18
1 <= w = 10^9

考察

1. 頂点が10^18なので、全頂点を持っておくのはメモリが足りない
2. クエリの数がそんなに多くないので、一部の頂点しか使わないかも
3. map使って、LCA的なことをやれば解けそう？？

ある頂点iの親は、i/2小数点切り捨てとなる

4. クエリ1は、頂点の数を1/2しながら足していく
i -> i/2 -> (i/2)/2 -> ... -> 1
辺は開始点のものであるとして、開始点に辺のコストを足していく

共通の親が1では無い以下の様な場合
i -> i/2 -> ... -> k -> k/2 -> ... -> 1
j -> j/2 -> ... -> k -> k/2 -> ... -> 1
この時は、「k -> k/2 -> ... -> 1」でダブってコストを足しているので、その分引いておく

5. クエリ2も同様にやればできる

実装

http://codeforces.com/contest/697/submission/19122405

int q;
typedef long long ll;
//-----------------------------------------------------------------
int main() {
	cin >> q;
	map<ll, ll> m;
	rep(qq, 0, q) {
		int t; cin >> t;
		if (t == 1) {
			ll u, v, w; cin >> u >> v >> w;

			ll uu = u, vv = v;
			vector<ll> vec_u, vec_v;

			while (1 < uu) m[uu] += w, vec_u.push_back(uu), uu /= 2;
			while (1 < vv) m[vv] += w, vec_v.push_back(vv), vv /= 2;

			rep(i, 0, min(vec_u.size(), vec_v.size())) {
				int ui = vec_u.size() - 1 - i;
				int vi = vec_v.size() - 1 - i;
				if (vec_u[ui] == vec_v[vi])
					m[vec_u[ui]] -= w * 2;
				else
					break;
			}
		}
		else {
			ll u, v; cin >> u >> v;
			ll ret = 0;
			
			ll uu = u, vv = v;
			vector<ll> vec_u, vec_v;

			while (1 < uu) ret += m[uu], vec_u.push_back(uu), uu /= 2;
			while (1 < vv) ret += m[vv], vec_v.push_back(vv), vv /= 2;

			rep(i, 0, min(vec_u.size(), vec_v.size())) {
				int ui = vec_u.size() - 1 - i;
				int vi = vec_v.size() - 1 - i;
				if (vec_u[ui] == vec_v[vi])
					ret -= m[vec_u[ui]] * 2;
				else
					break;
			}
			cout << ret << endl;
		}
	}
}