#6396. 「THUPC2018」弗雷兹的玩具商店 / Toyshop

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

物是人非事事休,欲语泪先流。

弗雷兹在 C 市有一个玩具店,店里有 n 种玩具,编号依次为 1,2,\dots, n ,编号为 i 的玩具的单价为 c_i 元,一个该玩具提供的愉悦度为 v_i

突然有一天,C市来了 m 个小朋友。据可靠消息,这些小朋友会在一些时刻一起来店里买东西,其中第 i 个小朋友每次都会带 i 元( 1\leq i\leq m )。

由于某些玩具特别优秀,所以每次小朋友们都会在特定的编号范围内挑选玩具。

除此之外,由于小朋友们在一年前的清华校赛中就愉悦得无法自拔,所以弗雷兹放弃了对他们的治疗,于是小朋友们就可以无限制地购买玩具了。也就是说,对于任意玩具,每个小朋友在每次的购买件数都可以是任意的非负整数。

时代飞速发展,玩具的受欢迎程度和价格也会随着时代的发展而改变。

为了方便你处理这些信息,Yazid 进行了整理,发现这些日子里,弗雷兹的玩具商店里共发生了 Q 个事件。

对于每个事件,都有 3 个基本参数 op,l,r 。其中 op 1 3 之间的整数,代表了事件的类别:

  1. 对于 op=1 的事件,Yazid 还会给你一个额外参数 d ,表示这是一个价格调整事件:将编号在区间 [l,r] 内的玩具的单价 c 全部增加 d 元。为了防止单价超过 m 元导致玩具永远无法被小朋友们购买,弗雷兹会将所有超过 m 的单价减去 m 。(保证 d 为不超过 m 的正数)

  2. 对于 op=2 的事件,Yazid还会给你一个额外参数 b ,表示这是一个愉悦修正事件:将编号在区间 [l,r] 内的玩具的愉悦度 v 全部增加 b 。(需要注意这里的 b 可能是负数)

  3. 对于 op=3​ 的事件,表示购买事件:所有的 m​ 个小朋友来到弗雷兹的玩具商店,在编号范围在 [l,r]​ 内的玩具中进行随意地购买。

现在,对于每一次的购买事件,你想知道:

  1. 所有小朋友所能获得的最大愉悦度之和。

  2. 所有小朋友所能获得的最大愉悦度的异或和(异或运算是 \mathrm{xor} 运算,即 C++/Java/Python 中的 ^ 运算)。

输入格式

  • 1 2 个正整数 n,m ,分别表示玩具数量、以及小朋友的数量。

  • 2 n 个正整数 c_1,\dots,c_n ,依次描述各玩具的单价。

  • 3 n 个正整数 v_1,\dots,v_n ,依次描述各玩具的愉悦度。

  • 4 1 个非负整数 Q ,表示事件的数量。

  • 接下来 Q 行依次描述所有事件,每行描述一个事件。每行的开头是 3 个整数 op,l,r ,意义见题目描述。

    • 如果 op=1 ,接下来跟随 1 个该事件的额外参数(整数) d ,意义见题目描述。

    • 如果 op=2 ,接下来跟随 1 个该事件的额外参数(整数) b ,意义见题目描述。

    • 如果 op=3 ,接下来无任何额外参数。

    • 保证 1\leq l\leq r\leq n

对于每一行,如果包含多个数,则用单个空格将它们隔开。

输出格式

  • 对于每个购买事件,输出一行 2 个用空格隔开的整数,依次表示所有小朋友所能获得的最大愉悦度之和、以及所有小朋友所能获得的最大愉悦度的异或和。

样例

样例输入 1

4 10
1 6 10 2
100 2333 666 300
7
3 1 4
3 1 3
1 2 4 1
3 1 4
2 2 3 -1000
2 2 3 -600
3 2 4

样例输出 1

15165 2865
14165 2169
36630 798
4899 1273

样例解释 1

对于第 1 个购买事件,各位小朋友(编号从小到大,即从 1 10 )能够获得的最大愉悦度依次为: 100,300,400,600,700,2333,2433,2633,2733,2933

对于第 2 个购买事件,各位小朋友(编号从小到大,即从 1 10 )能够获得的最大愉悦度依次为: 100,200,300,400,500,2333,2433,2533,2633,2733

对于第 3 个购买事件,各位小朋友(编号从小到大,即从 1 10 )能够获得的最大愉悦度依次为: 666,1332,1998,2664,3330,3996,4662,5328,5994,6660

对于第 4 个购买事件,各位小朋友(编号从小到大,即从 1 10 )能够获得的最大愉悦度依次为: 0,0,300,300,300,600,733,733,900,1033

根据这些信息,你将很容易计算出答案。

数据范围与提示

保证 1\le n\leq 200,000 1\le m\leq 60 0\le Q\leq 30,000

保证 1\leq c_i,d\leq m

保证 0\leq v_i\leq 10^7 \left| b\right|\leq 10^3

提示

这个提示本不该有,但善良的出题人还是想提醒你:所有小朋友所能获得的最大愉悦度之和有可能超过 32 位有符号整数的范围。

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。