#P4231. 三步必杀

三步必杀

题目背景

(三)旧都

离开狭窄的洞穴,眼前豁然开朗。

天空飘着不寻常的雪花。

一反之前的幽闭,现在面对的,是繁华的街市,可以听见酒碗碰撞的声音。

这是由被人们厌恶的鬼族和其他妖怪们组成的小社会,一片其乐融融的景象。

诶,不远处突然出现了一些密密麻麻的小点,好像大颗粒扬尘一样。

离得近了点,终于看清楚了。

长着角的鬼们聚在一起,围观着另一只鬼的表演。

那”扬尘”,其实都是弹幕。

勇仪的招数之一,三步之内,所到之处弹幕云集,几乎没有生存可能。

为了强化这一技能,勇仪将对着一排柱子进行攻击。

旧地狱的柱子虽然无比坚固,但保险起见还是先要了解一下这样一套攻击对柱子有多少损伤,顺带也能检验练习的效果。

勇仪决定和其它鬼们商量商量...

“我知道妖怪之山的河童一族有一种叫做计算机的神奇道具,说不定可以借来用用”,萃香说道。

于是旧地狱的鬼族就决定请河城荷取来帮忙了。

“要记录【所有柱子的损伤程度】吗”,荷取问道。

经过进一步的询问,荷取发现他们仅仅需要【所有攻击都完成后】柱子的损伤程度。

任务了解地差不多了,荷取将其中的重要部分提取了出来,记录在了她的工作笔记本上:

(记录的内容见题目描述)

那么实验就这样开始了。

在惊天动地的碰撞声中,勇仪每完成一轮攻击,荷取都忠实地记录下对每根柱子产生的伤害。而此时勇仪就在旁边等待着记录完成,然后再进行下一轮的攻击。

地面上,天色渐晚。

“不想在这里留到深夜啊,不然就回不了家了”,荷取这样想着,手中依然在重复地向计算机中输入新产生的信息。

“真的必须一次一次地记录下每轮攻击对每个柱子产生的伤害吗?有没有更高效的方法?”这一念头在荷取的心中闪过...

(后续剧情在题解中,接下来请看T3)

题目描述

NN 个柱子排成一排,一开始每个柱子损伤度为 00

接下来勇仪会进行 MM 次攻击,每次攻击可以用 44 个参数 l,r,s,el,r,s,e 来描述:

表示这次攻击作用范围为第 ll 个到第 rr 个之间所有的柱子(包含 l,rl,r),对第一个柱子的伤害为 ss,对最后一个柱子的伤害为 ee

攻击产生的伤害值是一个等差数列。若 l=1,r=5,s=2,e=10l=1,r=5,s=2,e=10,则对第 151 \sim 5 个柱子分别产生 2,4,6,8,102,4,6,8,10 的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

输入格式

第一行 22 个整数 N,MN,M,用空格隔开,下同。

接下来 MM 行,每行4个整数 l,r,s,el,r,s,e,含义见题目描述。

数据保证对每个柱子产生的每次伤害值都是整数。

输出格式

由于输出数据可能过大无法全部输出,为了确保你真的能维护所有柱子的损伤度,只要输出它们的异或和与最大值即可。

(异或和就是所有数字按位异或起来的值。)

(异或运算符在 c++ 里为 ^。)

5 2
1 5 2 10
2 4 1 1

3 10
6 2
1 5 2 10
2 4 1 1
3 10

提示

样例解释:

样例 11

第一次攻击产生的伤害:2,4,6,8,102,4,6,8,10

第二次攻击产生的伤害:0,1,1,1,00,1,1,1,0

所有攻击结束后每个柱子的损伤程度:2,5,7,9,102,5,7,9,10

输出异或和与最大值,就是 3,103,10

样例 22

没有打到第六根柱子,答案不变

数据范围:

本题满分为 100100 分,下面是 44 个子任务。(x/y)表示(得分/测试点数量)。

妖精级(18/3):1n,m10001 \le n,m \le 1000。这种工作即使像妖精一样玩玩闹闹也能完成吧?

河童级(10/1):s=es=e,这可以代替我工作吗?

天狗级(20/4):1n,m1051 \le n,m \le 10^5。小打小闹不再可行了呢。

鬼神级(52/2):没有特殊限制。要真正开始思考了。

以上四部分数据不相交。

对于全部的数据:1n1071\le n\le 10^71m3×1051\le m\le 3\times 10^51l<rn1\le l < r \le n.

所有输入输出数据以及柱子受损伤程度始终在 [0,9×1018][0,9 \times 10^{18}] 范围内。

提示:

由于种种原因,时间限制可能会比较紧,c++ 选手请不要使用 cin 读入数据。

by orangebird。