git.cpp

#include <bits/stdc++.h>

#define FI first
#define SE second

typedef long long ll;
typedef std::pair<ll,ll> pairll;

const int rot_delta[4] = {3,0,0,1};

inline ll gilbert_order(int x, int y, int pow, int rotate) {
	if (pow == 0) return 0;

	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);

	seg = (seg + rotate) & 3;
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rot_delta[seg]) & 3;
	long long sub_square_size = 1LL << (2 * pow - 2);
	long long ans = seg * sub_square_size;
	long long add = gilbert_order(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (sub_square_size - add - 1);
	return ans;
}

struct fenwick {
    const ll n;
    ll *bit;
    fenwick(const ll& _n) : n(_n), bit(new ll[n+1]()) {}
    ~fenwick(void) {delete [] bit;}
    void add(ll i, const ll& v) {for (; i <= n; i += (i&-i)) bit[i] += v;}
    ll sum(ll h) {ll ret = 0; for (; h; h -= (h & -h)) ret += bit[h]; return ret;}
};

struct bg_query {
	int type;
	std::string arg1, arg2;
	ll lines;
	std::vector<pairll> ranges;
} queries[100001];

struct bg_range {
	ll l, r, id, ord;
	std::string branch;
	bool operator<(const bg_range& o) const {
		return ord < o.ord;
	}
} ranges[100001];


ll node_count = 1;
std::unordered_map<std::string, ll> node_ids;
std::vector<ll> gr[100001];
ll ans[100001], pre[100001], skip[100001];

ll po = 0;
void dfs(const ll& cur) {
	pre[cur] = po++;
	for (const auto& nei : gr[cur])
		dfs(nei);
	skip[cur] = po-1;
}

int main(void) {

	node_ids.reserve(50000);
	node_ids.max_load_factor(0.25);

	ll n; std::cin >> n;
	for (ll i = 0; i < n; ++i) {
		std::string str; std::cin >> str;
		if (str == "new") queries[i].type = 1;
		else if (str == "commit") queries[i].type = 2;
		else queries[i].type = 3;

		if (queries[i].type == 1) {
			std::cin >> queries[i].arg1;
			gr[0].push_back(node_ids[queries[i].arg1] = node_count++);
		} else if (queries[i].type == 2) {
			std::cin >> queries[i].arg1 >> queries[i].lines;
		} else {
			std::cin >> queries[i].arg1 >> queries[i].arg2;
			gr[node_ids[queries[i].arg1]].push_back(node_ids[queries[i].arg2] = node_count++);
		}
	}

	dfs(0);

	node_count = 1;
	for (ll i = 0; i < n; ++i) {
		if (queries[i].type == 2) {
			const ll me = node_ids[queries[i].arg1];
			queries[i].ranges.push_back(pairll{pre[me], pre[me]});
			auto first_it = std::lower_bound(gr[me].begin(), gr[me].end(), node_count);
			if (first_it != gr[me].end())
				queries[i].ranges.push_back(pairll{pre[*first_it], skip[me]});
		} else {
			node_count++;
		}
	}

	ll q; std::cin >> q;
	for (ll i = 0; i < q; ++i) {
		std::cin >> ranges[i].l >> ranges[i].r >> ranges[i].branch;
		ranges[i].id = i;
		ranges[i].ord = gilbert_order(--ranges[i].l, --ranges[i].r, 18, 0);
	}

	std::sort(ranges, ranges + q);

	fenwick mybit(node_count + 3);

	auto add = [&](const ll& i) {
		if (queries[i].type == 2)
			for (const auto& rr : queries[i].ranges) {
				mybit.add(rr.FI+1, +queries[i].lines);
				mybit.add(rr.SE+2, -queries[i].lines);
			}
	};

	auto rem = [&](const ll& i) {
		if (queries[i].type == 2)
			for (const auto& rr : queries[i].ranges) {
				mybit.add(rr.FI+1, -queries[i].lines);
				mybit.add(rr.SE+2, +queries[i].lines);
			}
	};

	ll l = 0, r = -1;

	for (ll i = 0; i < q; ++i) {
		while (l < ranges[i].l)
			rem(l++);
		while (l > ranges[i].l)
			add(--l);
		while (r < ranges[i].r)
			add(++r);
		while (r > ranges[i].r)
			rem(r--);
		ans[ranges[i].id] = mybit.sum(pre[node_ids[ranges[i].branch]]+1);
	}

	for (ll i = 0; i < q; ++i)
		std::cout << ans[i] << "\n";

	return 0;
}