#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();
unsigned hash_f(unsigned x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
struct chash {
ll operator()(ll x) const { return hash_f(x); }
};
const ll N = 1e18;
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;
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;
}
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;
Node *rmq = newNode();
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 (ll i = 0; i < ans1.size(); i++) {
assert(ans1[i] == ans2[i]);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnJhbmRvbV9kZXZpY2UgcmQ7Cm10MTk5Mzcgcm5nKDApOwp1bmlmb3JtX2ludF9kaXN0cmlidXRpb248bGw+IHVuaSgxLCAxZTkpOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBwaWk7Cgpjb25zdCBsbCByZHNlZWQgPSAodWludDY0X3QpKG1ha2VfdW5pcXVlPGNoYXI+KCkuZ2V0KCkpIF4gY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpOwoKdW5zaWduZWQgaGFzaF9mKHVuc2lnbmVkIHgpIHsKICAgIHggPSAoKHggPj4gMTYpIF4geCkgKiAweDQ1ZDlmM2I7CiAgICB4ID0gKCh4ID4+IDE2KSBeIHgpICogMHg0NWQ5ZjNiOwogICAgeCA9ICh4ID4+IDE2KSBeIHg7CiAgICByZXR1cm4geDsKfQoKc3RydWN0IGNoYXNoIHsKICAgIGxsIG9wZXJhdG9yKCkobGwgeCkgY29uc3QgeyByZXR1cm4gaGFzaF9mKHgpOyB9Cn07Cgpjb25zdCBsbCBOID0gMWUxODsKY29uc3QgbGwgTlVNX0VMRU0gPSAyZTU7CmNvbnN0IGxsIE5VTV9RVUVSSUVTID0gMmU1OwpzdHJ1Y3QgTm9kZSB7CiAgICBOb2RlICpscCwgKnJwOwogICAgbGwgc3VtOwp9OwppbmxpbmUgbGwgZXZhbChOb2RlICpwKSB7IHJldHVybiBwID8gcC0+c3VtIDogMExMOyB9Cgpjb25zdCBsbCBidWZTaXplID0gTlVNX0VMRU0gKiAzMTsKTm9kZSBidWZbYnVmU2l6ZV07Ck5vZGUgKm5ld05vZGUoKSB7CiAgICBzdGF0aWMgYXV0byBwdHIgPSBidWY7CiAgICByZXR1cm4gcHRyKys7Cn0KCmxsIGdldFN1bShOb2RlICpjdXIsIGxsIGwsIGxsIHIsIGxsIHgsIGxsIHkpIHsKICAgIGlmICghY3VyIHx8IHggPiByIHx8IHkgPCBsKQogICAgICAgIHJldHVybiAwOwogICAgaWYgKHggPD0gbCAmJiByIDw9IHkpIHsKICAgICAgICByZXR1cm4gY3VyLT5zdW07CiAgICB9CiAgICBsbCBtID0gKGwgKyByKSAvIDI7CiAgICByZXR1cm4gZ2V0U3VtKGN1ci0+bHAsIGwsIG0sIHgsIHkpICsgZ2V0U3VtKGN1ci0+cnAsIG0gKyAxLCByLCB4LCB5KTsKfQp2b2lkIHVwZGF0ZShOb2RlIComY3VyLCBsbCBsLCBsbCByLCBsbCBwb3MsIGxsIHZhbCkgewogICAgaWYgKCFjdXIpCiAgICAgICAgY3VyID0gbmV3Tm9kZSgpOwogICAgaWYgKGwgPT0gcikgewogICAgICAgIGN1ci0+c3VtID0gdmFsOwogICAgfSBlbHNlIHsKICAgICAgICBsbCBtID0gKGwgKyByKSAvIDI7CiAgICAgICAgaWYgKHBvcyA8PSBtKSB7CiAgICAgICAgICAgIHVwZGF0ZShjdXItPmxwLCBsLCBtLCBwb3MsIHZhbCk7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgdXBkYXRlKGN1ci0+cnAsIG0gKyAxLCByLCBwb3MsIHZhbCk7CiAgICAgICAgfQogICAgICAgIGN1ci0+c3VtID0gZXZhbChjdXItPmxwKSArIGV2YWwoY3VyLT5ycCk7CiAgICB9Cn0KTm9kZSAqcm9vdDsKCmdwX2hhc2hfdGFibGU8bGwsIGxsLCBjaGFzaD4gc2VnOwoKbGwgZ2V0KGxsIHgpIHsKICAgIGF1dG8gcmVzID0gc2VnLmZpbmQoeCk7CiAgICByZXR1cm4gKHJlcyA9PSBzZWcuZW5kKCkpID8gMCA6IHJlcy0+c2Vjb25kOwogICAgLy8gcmV0dXJuIChzZWcuZmluZCh4KSA9PSBzZWcuZW5kKCkpID8gMCA6IHNlZ1t4XTsKfQp2b2lkIG1vZGlmeShsbCBwLCBsbCB2YWwpIHsKICAgIGZvciAoc2VnW3AgKz0gTl0gPSB2YWw7IHAgPiAwOyBwID4+PSAxKSB7CiAgICAgICAgc2VnW3AgPj4gMV0gPSBnZXQocCkgKyBnZXQocCBeIDEpOwogICAgfQp9CgpsbCBxdWVyeShsbCBsLCBsbCByKSB7CiAgICBsbCByZXMgPSAwOwogICAgZm9yIChsICs9IE4sIHIgKz0gTjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEpIHsKICAgICAgICBpZiAobCAmIDEpCiAgICAgICAgICAgIHJlcyArPSBnZXQobCsrKTsKICAgICAgICBpZiAociAmIDEpCiAgICAgICAgICAgIHJlcyArPSBnZXQoLS1yKTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgdmVjdG9yPHBpaT4gZWxlbXM7CiAgICBmb3IgKGxsIGkgPSAwOyBpIDwgTlVNX0VMRU07IGkrKykgewogICAgICAgIGVsZW1zLnB1c2hfYmFjayh7dW5pKHJuZyksIHVuaShybmcpfSk7CiAgICB9CiAgICB2ZWN0b3I8cGlpPiBxdWVyaWVzOwogICAgZm9yIChsbCBpID0gMDsgaSA8IE5VTV9RVUVSSUVTOyBpKyspIHsKICAgICAgICBsbCBhID0gdW5pKHJuZyksIGIgPSB1bmkocm5nKTsKICAgICAgICBpZiAoYSA+IGIpCiAgICAgICAgICAgIHN3YXAoYSwgYik7CiAgICAgICAgcXVlcmllcy5wdXNoX2JhY2soe2EsIGJ9KTsKICAgIH0KICAgIHZlY3RvcjxsbD4gYW5zMSwgYW5zMjsKICAgIGNsb2NrX3QgYmVnaW47CiAgICBOb2RlICpybXEgPSBuZXdOb2RlKCk7CiAgICBiZWdpbiA9IGNsb2NrKCk7CiAgICBmb3IgKGF1dG8gaSA6IGVsZW1zKSB7CiAgICAgICAgbW9kaWZ5KGkuZmlyc3QsIGkuc2Vjb25kKTsKICAgIH0KICAgIGZvciAoYXV0byBpIDogcXVlcmllcykgewogICAgICAgIGFuczIucHVzaF9iYWNrKHF1ZXJ5KGkuZmlyc3QsIGkuc2Vjb25kICsgMSkpOwogICAgfQogICAgY291dCA8PCAicG9saWN5IGhhc2g6ICIgPDwgKGRvdWJsZSkoY2xvY2soKSAtIGJlZ2luKSAvIENMT0NLU19QRVJfU0VDIDw8IGVuZGw7CiAgICBzZWcuY2xlYXIoKTsKCiAgICBiZWdpbiA9IGNsb2NrKCk7CiAgICBmb3IgKGF1dG8gaSA6IGVsZW1zKSB7CiAgICAgICAgdXBkYXRlKHJvb3QsIDEsIE4sIGkuZmlyc3QsIGkuc2Vjb25kKTsKICAgIH0KICAgIGZvciAoYXV0byBpIDogcXVlcmllcykgewogICAgICAgIGFuczEucHVzaF9iYWNrKGdldFN1bShyb290LCAxLCBOLCBpLmZpcnN0LCBpLnNlY29uZCkpOwogICAgfQogICAgY291dCA8PCAicG9pbnRlcjogIiA8PCAoZG91YmxlKShjbG9jaygpIC0gYmVnaW4pIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgZW5kbDsKICAgIGZvciAobGwgaSA9IDA7IGkgPCBhbnMxLnNpemUoKTsgaSsrKSB7CiAgICAgICAgYXNzZXJ0KGFuczFbaV0gPT0gYW5zMltpXSk7CiAgICB9Cn0=