Created
August 26, 2018 04:01
-
-
Save c650/2621e57e7b854906659054e767a4a00d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment