#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pii;
uniform_int_distribution<ll> uni(1, 1e9);
random_device rd;
mt19937 rng(0);
const int rdseed = (uint64_t)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
const ll N = 1e9;
const ll NUM_ELEM = 2e5;
const ll NUM_QUERIES = 2e5;
/***************************************************/
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;
/***************************************************/
int hash_f(int x) { return ((x >> 16) ^ x) * 0x45d9f3b; }
struct chash {
int operator()(int x) const { return hash_f(x); }
};
gp_hash_table<ll, ll, chash> seg;
ll get(ll x) {
auto res = seg.find(x);
return (res == seg.end()) ? 0 : res->second;
// return (seg.find(x) == seg.end()) ? 0 : seg[x];
}
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;
}
/***************************************************/
int 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 << "policy 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 (int i = 0; i < ans1.size(); i++) {
assert(ans1[i] == ans2[i]);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxsbCwgbGw+IHBpaTsKdW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGxsPiB1bmkoMSwgMWU5KTsKcmFuZG9tX2RldmljZSByZDsKbXQxOTkzNyBybmcoMCk7CmNvbnN0IGludCByZHNlZWQgPSAodWludDY0X3QpKG1ha2VfdW5pcXVlPGNoYXI+KCkuZ2V0KCkpIF4gY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpOwoKY29uc3QgbGwgTiA9IDFlOTsKY29uc3QgbGwgTlVNX0VMRU0gPSAyZTU7CmNvbnN0IGxsIE5VTV9RVUVSSUVTID0gMmU1OwoKLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KCnN0cnVjdCBOb2RlIHsKCU5vZGUgKmxwLCAqcnA7CglsbCBzdW07Cn07CmlubGluZSBsbCBldmFsKE5vZGUqIHApIHsKCXJldHVybiBwID8gcC0+c3VtIDogMExMOwp9Cgpjb25zdCBsbCBidWZTaXplID0gTlVNX0VMRU0gKiAzMTsKTm9kZSBidWZbYnVmU2l6ZV07Ck5vZGUgKm5ld05vZGUoKSB7IAoJc3RhdGljIGF1dG8gcHRyID0gYnVmOwoJcmV0dXJuIHB0cisrOwp9CgpsbCBnZXRTdW0oTm9kZSogY3VyLCBsbCBsLCBsbCByLCBsbCB4LCBsbCB5KSB7CglpZiAoIWN1ciB8fCB4ID4gciB8fCB5IDwgbCkgcmV0dXJuIDA7CiAgICBpZiAoeCA8PSBsICYmIHIgPD0geSkgewogICAgICAgIHJldHVybiBjdXItPnN1bTsKICAgIH0KICAgIGxsIG0gPSAobCArIHIpIC8gMjsKICAgIHJldHVybiBnZXRTdW0oY3VyLT5scCwgbCwgbSwgeCwgeSkgKyBnZXRTdW0oY3VyLT5ycCwgbSArIDEsIHIsIHgsIHkpOwp9CnZvaWQgdXBkYXRlKE5vZGUqJiBjdXIsIGxsIGwsIGxsIHIsIGxsIHBvcywgbGwgdmFsKSB7CglpZiAoIWN1cikgY3VyID0gbmV3Tm9kZSgpOwoJaWYgKGwgPT0gcikgewoJCWN1ci0+c3VtID0gdmFsOwoJfSBlbHNlIHsKCQlsbCBtID0gKGwgKyByKSAvIDI7CgkJaWYgKHBvcyA8PSBtKSB7CgkJCXVwZGF0ZShjdXItPmxwLCBsLCBtLCBwb3MsIHZhbCk7CgkJfSBlbHNlIHsKCQkJdXBkYXRlKGN1ci0+cnAsIG0gKyAxLCByLCBwb3MsIHZhbCk7CgkJfQoJCWN1ci0+c3VtID0gZXZhbChjdXItPmxwKSArIGV2YWwoY3VyLT5ycCk7Cgl9Cn0KTm9kZSAqcm9vdDsKCi8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCgppbnQgaGFzaF9mKGludCB4KSB7IHJldHVybiAoKHggPj4gMTYpIF4geCkgKiAweDQ1ZDlmM2I7IH0KCnN0cnVjdCBjaGFzaCB7CiAgICBpbnQgb3BlcmF0b3IoKShpbnQgeCkgY29uc3QgeyByZXR1cm4gaGFzaF9mKHgpOyB9Cn07CgpncF9oYXNoX3RhYmxlPGxsLCBsbCwgY2hhc2g+IHNlZzsKCmxsIGdldChsbCB4KSB7CiAgICBhdXRvIHJlcyA9IHNlZy5maW5kKHgpOwogICAgcmV0dXJuIChyZXMgPT0gc2VnLmVuZCgpKSA/IDAgOiByZXMtPnNlY29uZDsKICAgIC8vIHJldHVybiAoc2VnLmZpbmQoeCkgPT0gc2VnLmVuZCgpKSA/IDAgOiBzZWdbeF07Cn0Kdm9pZCBtb2RpZnkobGwgcCwgbGwgdmFsKSB7CiAgICBmb3IgKHNlZ1twICs9IE5dID0gdmFsOyBwID4gMDsgcCA+Pj0gMSkgewogICAgICAgIHNlZ1twID4+IDFdID0gZ2V0KHApICsgZ2V0KHAgXiAxKTsKICAgIH0KfQoKbGwgcXVlcnkobGwgbCwgbGwgcikgewogICAgbGwgcmVzID0gMDsKICAgIGZvciAobCArPSBOLCByICs9IE47IGwgPCByOyBsID4+PSAxLCByID4+PSAxKSB7CiAgICAgICAgaWYgKGwgJiAxKQogICAgICAgICAgICByZXMgKz0gZ2V0KGwrKyk7CiAgICAgICAgaWYgKHIgJiAxKQogICAgICAgICAgICByZXMgKz0gZ2V0KC0tcik7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICB2ZWN0b3I8cGlpPiBlbGVtczsKICAgIGZvciAobGwgaSA9IDA7IGkgPCBOVU1fRUxFTTsgaSsrKSB7CiAgICAgICAgZWxlbXMucHVzaF9iYWNrKHt1bmkocm5nKSwgdW5pKHJuZyl9KTsKICAgIH0KICAgIHZlY3RvcjxwaWk+IHF1ZXJpZXM7CiAgICBmb3IgKGxsIGkgPSAwOyBpIDwgTlVNX1FVRVJJRVM7IGkrKykgewogICAgICAgIGxsIGEgPSB1bmkocm5nKSwgYiA9IHVuaShybmcpOwogICAgICAgIGlmIChhID4gYikKICAgICAgICAgICAgc3dhcChhLCBiKTsKICAgICAgICBxdWVyaWVzLnB1c2hfYmFjayh7YSwgYn0pOwogICAgfQogICAgdmVjdG9yPGxsPiBhbnMxLCBhbnMyOwogICAgY2xvY2tfdCBiZWdpbjsKICAgIGJlZ2luID0gY2xvY2soKTsKICAgIGZvciAoYXV0byBpIDogZWxlbXMpIHsKICAgICAgICBtb2RpZnkoaS5maXJzdCwgaS5zZWNvbmQpOwogICAgfQogICAgZm9yIChhdXRvIGkgOiBxdWVyaWVzKSB7CiAgICAgICAgYW5zMi5wdXNoX2JhY2socXVlcnkoaS5maXJzdCwgaS5zZWNvbmQgKyAxKSk7CiAgICB9CiAgICBjb3V0IDw8ICJwb2xpY3kgaGFzaDogIiA8PCAoZG91YmxlKShjbG9jaygpIC0gYmVnaW4pIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgZW5kbDsKICAgIHNlZy5jbGVhcigpOwogICAgYmVnaW4gPSBjbG9jaygpOwogICAgZm9yIChhdXRvIGkgOiBlbGVtcykgewogICAgICAgIHVwZGF0ZShyb290LCAxLCBOLCBpLmZpcnN0LCBpLnNlY29uZCk7CiAgICB9CiAgICBmb3IgKGF1dG8gaSA6IHF1ZXJpZXMpIHsKICAgICAgICBhbnMxLnB1c2hfYmFjayhnZXRTdW0ocm9vdCwgMSwgTiwgaS5maXJzdCwgaS5zZWNvbmQpKTsKICAgIH0KICAgIGNvdXQgPDwgInBvaW50ZXI6ICIgPDwgKGRvdWJsZSkoY2xvY2soKSAtIGJlZ2luKSAvIENMT0NLU19QRVJfU0VDIDw8IGVuZGw7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhbnMxLnNpemUoKTsgaSsrKSB7CiAgICAgICAgYXNzZXJ0KGFuczFbaV0gPT0gYW5zMltpXSk7CiAgICB9Cn0=