#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
random_device rd;
mt19937 rng(0);
uniform_int_distribution<ll> uni(1, 1e9);
typedef pair<ll, ll> pii;
const ll rdseed = (uint64_t)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
const ll N = 1e18;
const ll NUM_ELEM = 1e5;
const ll NUM_QUERIES = 1e5;
struct Node {
Node *lp, *rp;
ll sum;
};
inline ll eval(Node *p) { return p ? p->sum : 0LL; }
const ll bufSize = NUM_ELEM * 31;
Node buf[bufSize];
Node *newNode() {
static auto ptr = buf;
return ptr++;
}
ll getSum(Node *cur, ll l, ll r, ll x, ll y) {
if (!cur || x > r || y < l)
return 0;
if (x <= l && r <= y) {
return cur->sum;
}
ll m = (l + r) / 2;
return getSum(cur->lp, l, m, x, y) + getSum(cur->rp, m + 1, r, x, y);
}
void update(Node *&cur, ll l, ll r, ll pos, ll val) {
if (!cur)
cur = newNode();
if (l == r) {
cur->sum = val;
} else {
ll m = (l + r) / 2;
if (pos <= m) {
update(cur->lp, l, m, pos, val);
} else {
update(cur->rp, m + 1, r, pos, val);
}
cur->sum = eval(cur->lp) + eval(cur->rp);
}
}
Node *root;
uint64_t hash_f(uint64_t x) {
x ^= x >> 33;
x *= 0xff51afd7ed558ccd;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53;
x ^= x >> 33;
return x;
}
class custom_size_policy : public hash_exponential_size_policy<size_t> {
public:
custom_size_policy() : hash_exponential_size_policy(1 << 24, 2) {}
};
struct chash {
ll operator()(ll x) const { return hash_f(x); }
};
typedef gp_hash_table<ll, ll, chash, equal_to<ll>, direct_mask_range_hashing<ll>, linear_probe_fn<>,
hash_standard_resize_policy<custom_size_policy, hash_load_check_resize_trigger<true>, true>>
gp;
gp seg;
ll get(ll x) {
auto res = seg.find(x);
return (res == seg.end()) ? 0 : res->second;
}
void modify(ll p, ll val) {
for (seg[p += N] = val; p > 0; p >>= 1) {
seg[p >> 1] = get(p) + get(p ^ 1);
}
}
ll query(ll l, ll r) {
ll res = 0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l & 1)
res += get(l++);
if (r & 1)
res += get(--r);
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<pii> elems;
for (ll i = 0; i < NUM_ELEM; i++) {
elems.push_back({uni(rng), uni(rng)});
}
vector<pii> queries;
for (ll i = 0; i < NUM_QUERIES; i++) {
ll a = uni(rng), b = uni(rng);
if (a > b)
swap(a, b);
queries.push_back({a, b});
}
vector<ll> ans1, ans2;
clock_t begin;
begin = clock();
for (auto i : elems) {
modify(i.first, i.second);
}
for (auto i : queries) {
ans2.push_back(query(i.first, i.second + 1));
}
cout << "hash: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
seg.clear();
begin = clock();
for (auto i : elems) {
update(root, 1, N, i.first, i.second);
}
for (auto i : queries) {
ans1.push_back(getSum(root, 1, N, i.first, i.second));
}
cout << "pointer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
for (ll i = 0; i < ans1.size(); i++) {
assert(ans1[i] == ans2[i]);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnJhbmRvbV9kZXZpY2UgcmQ7Cm10MTk5Mzcgcm5nKDApOwp1bmlmb3JtX2ludF9kaXN0cmlidXRpb248bGw+IHVuaSgxLCAxZTkpOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBwaWk7Cgpjb25zdCBsbCByZHNlZWQgPSAodWludDY0X3QpKG1ha2VfdW5pcXVlPGNoYXI+KCkuZ2V0KCkpIF4gY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpOwoKY29uc3QgbGwgTiA9IDFlMTg7CmNvbnN0IGxsIE5VTV9FTEVNID0gMWU1Owpjb25zdCBsbCBOVU1fUVVFUklFUyA9IDFlNTsKc3RydWN0IE5vZGUgewogICAgTm9kZSAqbHAsICpycDsKICAgIGxsIHN1bTsKfTsKaW5saW5lIGxsIGV2YWwoTm9kZSAqcCkgeyByZXR1cm4gcCA/IHAtPnN1bSA6IDBMTDsgfQoKY29uc3QgbGwgYnVmU2l6ZSA9IE5VTV9FTEVNICogMzE7Ck5vZGUgYnVmW2J1ZlNpemVdOwpOb2RlICpuZXdOb2RlKCkgewogICAgc3RhdGljIGF1dG8gcHRyID0gYnVmOwogICAgcmV0dXJuIHB0cisrOwp9CgpsbCBnZXRTdW0oTm9kZSAqY3VyLCBsbCBsLCBsbCByLCBsbCB4LCBsbCB5KSB7CiAgICBpZiAoIWN1ciB8fCB4ID4gciB8fCB5IDwgbCkKICAgICAgICByZXR1cm4gMDsKICAgIGlmICh4IDw9IGwgJiYgciA8PSB5KSB7CiAgICAgICAgcmV0dXJuIGN1ci0+c3VtOwogICAgfQogICAgbGwgbSA9IChsICsgcikgLyAyOwogICAgcmV0dXJuIGdldFN1bShjdXItPmxwLCBsLCBtLCB4LCB5KSArIGdldFN1bShjdXItPnJwLCBtICsgMSwgciwgeCwgeSk7Cn0Kdm9pZCB1cGRhdGUoTm9kZSAqJmN1ciwgbGwgbCwgbGwgciwgbGwgcG9zLCBsbCB2YWwpIHsKICAgIGlmICghY3VyKQogICAgICAgIGN1ciA9IG5ld05vZGUoKTsKICAgIGlmIChsID09IHIpIHsKICAgICAgICBjdXItPnN1bSA9IHZhbDsKICAgIH0gZWxzZSB7CiAgICAgICAgbGwgbSA9IChsICsgcikgLyAyOwogICAgICAgIGlmIChwb3MgPD0gbSkgewogICAgICAgICAgICB1cGRhdGUoY3VyLT5scCwgbCwgbSwgcG9zLCB2YWwpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHVwZGF0ZShjdXItPnJwLCBtICsgMSwgciwgcG9zLCB2YWwpOwogICAgICAgIH0KICAgICAgICBjdXItPnN1bSA9IGV2YWwoY3VyLT5scCkgKyBldmFsKGN1ci0+cnApOwogICAgfQp9Ck5vZGUgKnJvb3Q7Cgp1aW50NjRfdCBoYXNoX2YodWludDY0X3QgeCkgewogICAgeCBePSB4ID4+IDMzOwogICAgeCAqPSAweGZmNTFhZmQ3ZWQ1NThjY2Q7CiAgICB4IF49IHggPj4gMzM7CiAgICB4ICo9IDB4YzRjZWI5ZmUxYTg1ZWM1MzsKICAgIHggXj0geCA+PiAzMzsKICAgIHJldHVybiB4Owp9CmNsYXNzIGN1c3RvbV9zaXplX3BvbGljeSA6IHB1YmxpYyBoYXNoX2V4cG9uZW50aWFsX3NpemVfcG9saWN5PHNpemVfdD4gewogIHB1YmxpYzoKICAgIGN1c3RvbV9zaXplX3BvbGljeSgpIDogaGFzaF9leHBvbmVudGlhbF9zaXplX3BvbGljeSgxIDw8IDI0LCAyKSB7fQp9OwoKc3RydWN0IGNoYXNoIHsKICAgIGxsIG9wZXJhdG9yKCkobGwgeCkgY29uc3QgeyByZXR1cm4gaGFzaF9mKHgpOyB9Cn07Cgp0eXBlZGVmIGdwX2hhc2hfdGFibGU8bGwsIGxsLCBjaGFzaCwgZXF1YWxfdG88bGw+LCBkaXJlY3RfbWFza19yYW5nZV9oYXNoaW5nPGxsPiwgbGluZWFyX3Byb2JlX2ZuPD4sCiAgICAgICAgICAgICAgICAgICAgICBoYXNoX3N0YW5kYXJkX3Jlc2l6ZV9wb2xpY3k8Y3VzdG9tX3NpemVfcG9saWN5LCBoYXNoX2xvYWRfY2hlY2tfcmVzaXplX3RyaWdnZXI8dHJ1ZT4sIHRydWU+PgogICAgZ3A7CgpncCBzZWc7CmxsIGdldChsbCB4KSB7CiAgICBhdXRvIHJlcyA9IHNlZy5maW5kKHgpOwogICAgcmV0dXJuIChyZXMgPT0gc2VnLmVuZCgpKSA/IDAgOiByZXMtPnNlY29uZDsKfQp2b2lkIG1vZGlmeShsbCBwLCBsbCB2YWwpIHsKICAgIGZvciAoc2VnW3AgKz0gTl0gPSB2YWw7IHAgPiAwOyBwID4+PSAxKSB7CiAgICAgICAgc2VnW3AgPj4gMV0gPSBnZXQocCkgKyBnZXQocCBeIDEpOwogICAgfQp9CgpsbCBxdWVyeShsbCBsLCBsbCByKSB7CiAgICBsbCByZXMgPSAwOwogICAgZm9yIChsICs9IE4sIHIgKz0gTjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEpIHsKICAgICAgICBpZiAobCAmIDEpCiAgICAgICAgICAgIHJlcyArPSBnZXQobCsrKTsKICAgICAgICBpZiAociAmIDEpCiAgICAgICAgICAgIHJlcyArPSBnZXQoLS1yKTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgdmVjdG9yPHBpaT4gZWxlbXM7CiAgICBmb3IgKGxsIGkgPSAwOyBpIDwgTlVNX0VMRU07IGkrKykgewogICAgICAgIGVsZW1zLnB1c2hfYmFjayh7dW5pKHJuZyksIHVuaShybmcpfSk7CiAgICB9CiAgICB2ZWN0b3I8cGlpPiBxdWVyaWVzOwogICAgZm9yIChsbCBpID0gMDsgaSA8IE5VTV9RVUVSSUVTOyBpKyspIHsKICAgICAgICBsbCBhID0gdW5pKHJuZyksIGIgPSB1bmkocm5nKTsKICAgICAgICBpZiAoYSA+IGIpCiAgICAgICAgICAgIHN3YXAoYSwgYik7CiAgICAgICAgcXVlcmllcy5wdXNoX2JhY2soe2EsIGJ9KTsKICAgIH0KICAgIHZlY3RvcjxsbD4gYW5zMSwgYW5zMjsKICAgIGNsb2NrX3QgYmVnaW47CiAgICBiZWdpbiA9IGNsb2NrKCk7CiAgICBmb3IgKGF1dG8gaSA6IGVsZW1zKSB7CiAgICAgICAgbW9kaWZ5KGkuZmlyc3QsIGkuc2Vjb25kKTsKICAgIH0KICAgIGZvciAoYXV0byBpIDogcXVlcmllcykgewogICAgICAgIGFuczIucHVzaF9iYWNrKHF1ZXJ5KGkuZmlyc3QsIGkuc2Vjb25kICsgMSkpOwogICAgfQogICAgY291dCA8PCAiaGFzaDogIiA8PCAoZG91YmxlKShjbG9jaygpIC0gYmVnaW4pIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgZW5kbDsKICAgIHNlZy5jbGVhcigpOwoKICAgIGJlZ2luID0gY2xvY2soKTsKICAgIGZvciAoYXV0byBpIDogZWxlbXMpIHsKICAgICAgICB1cGRhdGUocm9vdCwgMSwgTiwgaS5maXJzdCwgaS5zZWNvbmQpOwogICAgfQogICAgZm9yIChhdXRvIGkgOiBxdWVyaWVzKSB7CiAgICAgICAgYW5zMS5wdXNoX2JhY2soZ2V0U3VtKHJvb3QsIDEsIE4sIGkuZmlyc3QsIGkuc2Vjb25kKSk7CiAgICB9CiAgICBjb3V0IDw8ICJwb2ludGVyOiAiIDw8IChkb3VibGUpKGNsb2NrKCkgLSBiZWdpbikgLyBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogICAgZm9yIChsbCBpID0gMDsgaSA8IGFuczEuc2l6ZSgpOyBpKyspIHsKICAgICAgICBhc3NlcnQoYW5zMVtpXSA9PSBhbnMyW2ldKTsKICAgIH0KfQ==