P11615 【模板】哈希表
题目描述
你需要维护一个映射 $f: \left[0, 2^{64}\right) \to \left[0, 2^{64}\right)$。初始时,对于任意 x∈[0,264) 都有 f(x)=0。
一共有 n 次操作。第 i 次操作给出一个二元组 (xi,yi),含义是先查询当前 f(xi) 的值,随后将 f(xi) 赋值为 yi。
输入格式
第一行输入一个整数 n(1≦n≦5×105) 代表操作次数。
此后 n 行,第 i 行输入两个整数 xi,yi(0≦xi,yi<264) 代表第 i 次操作给出的二元组。
输出格式
为了减少输出量,设第 i 次操作查询得到的值为 ansi。你只需要在一行上输出 i=1∑ni×ansi 对 264 取模的结果。
测试样例
5
0 4
0 998244353
1000000000000000000 20120712
1000000000000000000 1000000000000000000
1000000000000000000 998244353
5000000000080482856
样例 1 解释
五次操作依次如下:
∙第 1 次操作:查询 f(0)=0,随后令 f(0)=4,因此 ans1=0;
∙第 2 次操作:查询 f(0)=4,随后令 f(0)=998244353,因此 ans2=4;
∙第 3 次操作:查询 f(1018)=0,随后令 f(1018)=20120712,因此 ans3=0;
∙第 4 次操作:查询 f(1018)=20120712,随后令 f(1018)=1018,因此 ans4=20120712;
∙第 5 次操作:查询 f(1018)=1018,随后令 f(1018)=998244353,因此 ans5=1018。
所以答案为 $1 \times 0 + 2 \times 4 + 3 \times 0 + 4 \times 20120712 + 5 \times 10^{18} = 5000000000080482856$。该值小于 264,取模后不变。
6
5 10
5 0
7 3
5 99
7 1
5 2
629
样例 2 解释
六次操作依次查询到 0,10,0,0,3,99,因此答案为 $2 \times 10 + 5 \times 3 + 6 \times 99 = 20 + 15 + 594 = 629$。
提示
本题的时限较为宽裕,O(nlogn) 的做法(例如用 std::map 直接维护,或先离散化再用 lower_bound 查找)都可以在时限内完成。
输入文件约为 20 MB,建议使用快速读入。下面给出一种基于 fread 的快速读入实现,可以直接读入 64 位无符号整数:
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;
}
本题按照 n 的大小划分了若干子任务,具体如下:
| 子任务 |
n |
| 0 |
≦10 |
| 1 |
≦105 |
| 2 |
≦5×105 |
子任务 1 与子任务 2 中包含针对 unordered_map、gp_hash_table、cc_hash_table 以及一些错误的哈希方式的 hack 数据,其余数据生成方式较为随机。
如果你认为自己的代码复杂度正确却没有通过,请记得使用快速读入。