#P18529. Fast Hash Transform

Fast Hash Transform

Fast Hash Transform

令 V={0,1,…,264−1}V=\{0,1,\ldots,2^{64}-1\}。定义 VV 上的函数 ff 是一个单轮散列函数,当且仅当它具有下列标准形式:

$$f(X)=B\oplus\bigoplus_{j=1}^{m}\bigl((\operatorname{ROL}_{64}(X,s_j))\circ_j A_j\bigr).$$

其中 Aj,B∈VA_j,B\in V,0≤m≤640\le m\le64,0≤sj≤630\le s_j\le63,同一个函数中的所有 sjs_j 两两不同;⊕\oplus 表示按位异或,∘j\circ_j 是按位或或按位与。ROL⁡64(X,s)\operatorname{ROL}_{64}(X,s) 表示将 XX 补足为 64 位无符号二进制表示后循环左移 ss 位:从最高位移出的位重新进入最低位。移位 00 位时保持不变。异或项为空时其值为 00,因此 m=0m=0 时 f(X)=Bf(X)=B。

给定 NN 个单轮散列函数 f1,f2,…,fNf_1,f_2,\ldots,f_N,以及 QQ 次操作,操作有以下两类:

  • 给定 l,r,xl,r,x,计算 fr(⋯(fl+1(fl(x)))⋯ )f_r(\cdots(f_{l+1}(f_l(x)))\cdots),即按下标从 ll 到 rr 依次应用函数。
  • 给定 ll,将 flf_l 修改为一个新的单轮散列函数。修改对其后的操作持续生效。

修改散列函数会使许多预计算结果失效,因此保证第二类操作最多 CC 次。

输入格式

第一行包含三个非负整数 N,Q,CN,Q,C。保证 1≤N,Q≤20 0001\le N,Q\le20\,000,0≤C≤4000\le C\le400,且 C<QC<Q。

接下来 NN 行,第 ii 行描述初始函数 fif_i。每行依次包含:

  1. 一个非负整数 mm,表示异或项的个数,0≤m≤640\le m\le64。
  2. 接下来 3m3m 个非负整数,按 s1,o1,A1,s2,o2,A2,…,sm,om,Ams_1,o_1,A_1,s_2,o_2,A_2,\ldots,s_m,o_m,A_m 的顺序给出。其中 0≤sj≤630\le s_j\le63,同一个函数中的移位量两两不同;oj=0o_j=0 表示按位或,oj=1o_j=1 表示按位与;0≤Aj<2640\le A_j<2^{64}。
  3. 最后一个非负整数 BB,0≤B<2640\le B<2^{64}。

再接下来 QQ 行,每行描述一次操作:

  • 0 l r x:输出从 flf_l 到 frf_r 的复合变换作用于 xx 的结果。保证 1≤l≤r≤N1\le l\le r\le N,0≤x<2640\le x<2^{64}。
  • 1 l m s1 o1 A1 ... sm om Am B:将 flf_l 替换为此行给出的新函数,函数参数的格式和限制与初始函数相同。保证 1≤l≤N1\le l\le N。

第二类操作不超过 CC 次。所有数均使用十进制表示。输入只有一组数据。

输出格式

对每次第一类操作,单独输出一行一个十进制整数,表示答案。答案属于 VV。

样例

输入:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

输出:

64206
2023
31
1112

样例说明

初始的三个函数分别为:

$$f_1(X)=\operatorname{ROL}_{64}(X,4)\oplus51966,\qquad f_2(X)=\operatorname{ROL}_{64}(X,60),\qquad f_3(X)=(X\mathbin{\vert}16)\oplus15.$$
  • 第一次操作:f1(771)=64206f_1(771)=64206。相应十六进制数为 771=0x0303771=\mathtt{0x0303}、51966=0xCAFE51966=\mathtt{0xCAFE}、64206=0xFACE64206=\mathtt{0xFACE}。
  • 第二次操作:f2(32368)=2023f_2(32368)=2023,其中 32368=0x7E7032368=\mathtt{0x7E70}、2023=0x07E72023=\mathtt{0x07E7}。
  • 第三次操作:f3(0)=31=0x001Ff_3(0)=31=\mathtt{0x001F},其中 16=0x001016=\mathtt{0x0010}、15=0x000F15=\mathtt{0x000F}。
  • 第四次操作后,$f_2(X)=(X\mathbin{\vert}15)\oplus(\operatorname{ROL}_{64}(X,61)\mathbin{\&}4095)\oplus46681$,其中 4095=0x0FFF4095=\mathtt{0x0FFF}、46681=0xB65946681=\mathtt{0xB659}。
  • 第五次操作中,f1(2023)=46222=0xB48Ef_1(2023)=46222=\mathtt{0xB48E},修改后的 f2(46222)=1095=0x0447f_2(46222)=1095=\mathtt{0x0447},f3(1095)=1112=0x0458f_3(1095)=1112=\mathtt{0x0458},故输出 11121112。

请注意输入输出效率。样例说明中十六进制数补为四位只是为了展示,不表示输入数不会超过 6553565535;实际数值可以达到 264−12^{64}-1。