LG#P11615. 【模板】哈希表

【模板】哈希表

P11615 【模板】哈希表

题目描述

\hspace{15pt}你需要维护一个映射 $f: \left[0, 2^{64}\right) \to \left[0, 2^{64}\right)$。初始时,对于任意 x∈[0,264)x \in \left[0, 2^{64}\right) 都有 f(x)=0f(x) = 0。

\hspace{15pt}一共有 nn 次操作。第 ii 次操作给出一个二元组 (xi,yi)(x_i, y_i),含义是先查询当前 f(xi)f(x_i) 的值,随后将 f(xi)f(x_i) 赋值为 yiy_i。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦5×105)n \left(1 \leqq n \leqq 5 \times 10^5\right) 代表操作次数。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 xi,yi(0≦xi,yi<264)x_i, y_i \left(0 \leqq x_i, y_i < 2^{64}\right) 代表第 ii 次操作给出的二元组。

输出格式

\hspace{15pt}为了减少输出量,设第 ii 次操作查询得到的值为 ansi\mathrm{ans}_i。你只需要在一行上输出 ∑i=1ni×ansi\sum\limits_{i=1}^{n} i \times \mathrm{ans}_i 对 2642^{64} 取模的结果。

测试样例

5
0 4
0 998244353
1000000000000000000 20120712
1000000000000000000 1000000000000000000
1000000000000000000 998244353
5000000000080482856

样例 1 解释

\hspace{15pt}五次操作依次如下:

∙ \hspace{23pt}\bullet\,第 11 次操作:查询 f(0)=0f(0) = 0,随后令 f(0)=4f(0) = 4,因此 ans1=0\mathrm{ans}_1 = 0;

∙ \hspace{23pt}\bullet\,第 22 次操作:查询 f(0)=4f(0) = 4,随后令 f(0)=998244353f(0) = 998244353,因此 ans2=4\mathrm{ans}_2 = 4;

∙ \hspace{23pt}\bullet\,第 33 次操作:查询 f(1018)=0f(10^{18}) = 0,随后令 f(1018)=20120712f(10^{18}) = 20120712,因此 ans3=0\mathrm{ans}_3 = 0;

∙ \hspace{23pt}\bullet\,第 44 次操作:查询 f(1018)=20120712f(10^{18}) = 20120712,随后令 f(1018)=1018f(10^{18}) = 10^{18},因此 ans4=20120712\mathrm{ans}_4 = 20120712;

∙ \hspace{23pt}\bullet\,第 55 次操作:查询 f(1018)=1018f(10^{18}) = 10^{18},随后令 f(1018)=998244353f(10^{18}) = 998244353,因此 ans5=1018\mathrm{ans}_5 = 10^{18}。

\hspace{15pt}所以答案为 $1 \times 0 + 2 \times 4 + 3 \times 0 + 4 \times 20120712 + 5 \times 10^{18} = 5000000000080482856$。该值小于 2642^{64},取模后不变。

6
5 10
5 0
7 3
5 99
7 1
5 2
629

样例 2 解释

\hspace{15pt}六次操作依次查询到 0,10,0,0,3,990, 10, 0, 0, 3, 99,因此答案为 $2 \times 10 + 5 \times 3 + 6 \times 99 = 20 + 15 + 594 = 629$。

提示

\hspace{15pt}本题的时限较为宽裕,O(nlog⁡n)O(n \log n) 的做法(例如用 std::map 直接维护,或先离散化再用 lower_bound 查找)都可以在时限内完成。

\hspace{15pt}输入文件约为 2020 MB,建议使用快速读入。下面给出一种基于 fread 的快速读入实现,可以直接读入 6464 位无符号整数:

char buf[1<<23],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline unsigned long long rd() {//读入一个 64 位无符号整数
	unsigned long long x=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch)) x=x*10+(ch^48),ch=gc();
	return x;
}

\hspace{15pt}本题按照 nn 的大小划分了若干子任务,具体如下:

子任务 nn
00 ≦10\leqq 10
11 ≦105\leqq 10^5
22 ≦5×105\leqq 5 \times 10^5

\hspace{15pt}子任务 11 与子任务 22 中包含针对 unordered_map、gp_hash_table、cc_hash_table 以及一些错误的哈希方式的 hack 数据,其余数据生成方式较为随机。

\hspace{15pt}如果你认为自己的代码复杂度正确却没有通过,请记得使用快速读入。