P4231 三步必杀

    • 180通过
    • 944提交
  • 题目提供者 oscar
  • 评测方式 云端评测
  • 标签 前缀和 差分 树状数组
  • 难度 提高+/省选-
  • 时空限制 500ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    (三)旧都

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

    天空飘着不寻常的雪花。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    那么实验就这样开始了。

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

    地面上,天色渐晚。

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

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

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

    题目描述

    问题摘要:

    $N$ 个柱子排成一排,一开始每个柱子损伤度为0。

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

    表示这次攻击作用范围为第 $l$ 个到第 $r$ 个之间所有的柱子(包含 $l$ , $r$ ),对第一个柱子的伤害为 $s$ ,对最后一个柱子的伤害为 $e$ 。

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

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

    输入输出格式

    输入格式:

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

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

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

    输出格式:

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

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

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

    输入输出样例

    输入样例#1: 复制
    5 2
    1 5 2 10
    2 4 1 1
    
    输出样例#1: 复制
    3 10
    输入样例#2: 复制
    6 2
    1 5 2 10
    2 4 1 1
    输出样例#2: 复制
    3 10

    说明

    样例解释:

    样例1:

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

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

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

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

    样例2:

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

    数据范围:

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

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

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

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

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

    以上四部分数据不相交。

    对于全部的数据: $1\leqslant n\leqslant10^7$ , $1\leqslant m\leqslant3\times 10^5$ , $1\leqslant l<r\leqslant n$ .

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

    提示:

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

    by orangebird

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。