#P5455. [THUPC2018] 弗雷兹的玩具商店

[THUPC2018] 弗雷兹的玩具商店

题目背景

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

题目描述

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

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

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

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

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

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

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

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

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

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

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

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

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

输入格式

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

  • 22nn 个正整数 c1,,cnc_1,\dots,c_n,依次描述各玩具的单价。

  • 33nn 个正整数 v1,,vnv_1,\dots,v_n,依次描述各玩具的愉悦度。

  • 4411 个非负整数 QQ,表示事件的数量。

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

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

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

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

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

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

输出格式

  • 对于每个购买事件,输出一行 22 个用空格隔开的整数,依次表示所有小朋友所能获得的最大愉悦度之和、以及所有小朋友所能获得的最大愉悦度的异或和。
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
15165 2865
14165 2169
36630 798
4899 1273

提示

样例解释

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

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

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

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

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

数据范围

保证 1n200,0001\le n\leq 200,0001m601\le m\leq 600Q30,0000\le Q\leq 30,000

保证 1ci,dm1\leq c_i,d\leq m

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

提示

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

版权信息

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

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