#P11772. 报社天狗

    ID: 10060 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>数论洛谷原创O2优化分块洛谷月赛整除分块

报社天狗

题目背景

因为天依想不到新歌歌词怎么写破防了,所以这题的主人公不是天依。

题目描述

新一期《文文。新闻》开售了!

nn^\dag妖怪排队购买《文文。新闻》,将她们依次编号 1n1\sim n,每一只妖怪会购买若干份。然而,她们购买《文文。新闻》并不是为了阅读,而是是为了送给所有编号是自己倍数的的妖怪一份(自己可以不留)。也就是说,对于 1n1\sim n 的每只妖怪,依次进行:当手上的《文文。新闻》数量足够时,不进行购买,直接赠送;而不够时便会先向文文购买至刚好足够,再进行赠送。

文文为了使收益最大化,为每只妖怪详细制定了价格方案。具体地,第 ii 只妖怪在已有 jj 份《文文。新闻》时再买一份花费的价钱是 ai×bj+1a_i\times b_{j+1},其中 a,ba,b 是两个从 11 开始的长为 106+110^6+1 的正整数序列。

现在文文需要一个合理的定价方案,她决定从 a,ba,b 全为 11 时开始调整。具体地,有以下三种操作:

  • 1 x 询问以当前的 a,ba,b 数组,n=xn=x 时文文能有多少营业额,因为结果可能很大,你需要求出答案对 2322^{32} 取模后的结果。
  • 2 x y 适当地调整 aa 数组的值:令 ax=ya_x=y
  • 3 x y 适当地调整 bb 数组的值:令 bx=yb_x=y

\dag:经查证,量词为『只』和『个』的情况均有出现,THBwiki 中『一只妖怪』的匹配量显著多于『一个妖怪』,于是本题中采用『只』,并不是出题人的种族歧视。

输入格式

第一行一个整数 TT 表示操作的数量。

2T+12\sim T+1 行,每行 2233 个整数,表示题目中的一次操作。

输出格式

每行一个整数,表示每次询问的获利对 2322^{32} 取模后的结果。

5
1 5
2 2 5
3 1 3
1 5
1 6
4
6
12

提示

样例解释

第一个询问中,n=5n=5,两个序列中所有的元素均为 1111 号妖怪买了 44 份报纸,每份报纸的收益都是 11,其他的妖怪都没有买报纸,总收益为 44

第二个询问中,有 n=5,a2=3,b1=5n=5,a_2=3,b_1=5,序列中其他元素均为 1111 号妖怪买了 44 份报纸,其中第 11 份报纸的收益是 33,第 22 份到第 44 份报纸的收益都是 11,其他的妖怪都没有买报纸,总收益为 66

第三个询问中,有 n=6,a2=3,b1=5n=6,a_2=3,b_1=5,序列中其他元素均为 11。让我们具体来看看这次询问中的过程:

  • 11 号妖怪需要送其他每个妖怪各一份报纸,但是她没有报纸。于是她需要买 55 份报纸。其中第一份报纸的收益是 a1×b1=3a_1\times b_1=3,第 22 份到第 55 份报纸的收益都是 11。然后她给了其他每个妖怪各一份报纸。

  • 22 号妖怪需要送 44 号妖怪和 66 号妖怪各一份报纸,她已经从 11 号妖怪手中获得了一份报纸。于是她还需要买 11 份报纸,这份报纸的收益是 a2×b2=5a_2\times b_2=5

  • 33 号妖怪需要送 66 号妖怪一份报纸,她已经从 11 号妖怪手中获得了一份报纸,不需要再买报纸。

  • 44 号妖怪到 66 号妖怪都不需要送出报纸,也不需要再买报纸。

总收益为 1212

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 100%100\% 的数据,1T1051 \leq T \leq 10^51x,n1061 \leq x,n\leq 10^61y1091\le y\le 10^9

对于不同的子任务,作如下约定:

子任务编号 特殊性质 子任务分值
11 没有修改操作 1010
22 第一种操作中的每个 nn 都相等 2020
33 n,T105n,T \leq 10^5 3030
44 4040