P2357 守墓人

    • 354通过
    • 814提交
  • 题目提供者 MedalPluS
  • 评测方式 云端评测
  • 标签 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    在一个荒凉的墓地上

    有一个令人尊敬的守墓人, 他看守的墓地从来

    没有被盗过, 所以人们很放心的把自己的先人的墓

    安顿在他那

    守墓人能看好这片墓地是必然而不是偶然.....

    因为....守墓人懂风水 0.0

    他把墓地分为主要墓碑和次要墓碑, 主要墓碑

    只能有 1 个, 守墓人把他记为 1 号, 而次要墓碑有

    n-1 个,守墓人将之编号为 2,3...n,所以构成了一个有 n 个墓碑的墓地。

    而每个墓碑有一个初始的风水值,这些风水值决定了墓地的风水的好坏,所以守墓人

    需要经常来查询这些墓碑。

    善于运用风水的守墓人,通过一次次逆天改命,使得自己拥有了无限寿命,没人知道

    他活了多久。

    这天,你幸运的拜访到了他,他要求你和他共同见证接下来几年他的战果,但不过他

    每次统计风水值之和都需要你来帮他计算,算错了他会要你命 QAQ

    风水也不是不可变,除非遭遇特殊情况,已知在接下来的 2147483647 年里,会有 n 次

    灾难,守墓人会有几个操作:

    1.将[l,r]这个区间所有的墓碑的风水值增加 k。

    2.将主墓碑的风水值增加 k

    3.将主墓碑的风水值减少 k

    4.统计[l,r]这个区间所有的墓碑的风水值之和

    5.求主墓碑的风水值

    上面也说了,很多人会把先人的墓安居在这里,而且守墓人活了很多世纪→_→,墓碑

    的数量会多的你不敢相信= =

    守墓人和善的邀请你帮他完成这些操作,要不然哪天你的旅馆爆炸了,天上下刀子.....

    为了活命,还是帮他吧

    输入输出格式

    输入格式:

    第一行,两个正整数 n,f 表示共有 n 块墓碑,并且在接下来的

    2147483647 年里,会有 f 次世界末日

    第二行,n 个正整数,表示第 i 块墓碑的风水值

    接下来 f 行,每行都会有一个针对世界末日的解决方案,如题所述,标记同题

    输出格式:

    输出会有若干行,对 4 和 5 的提问做出回答

    输入输出样例

    输入样例#1: 复制
    5 7
    0 0 0 0 0
    1 1 5 1
    1 1 3 3
    2 3
    3 1
    4 1 5
    2 1
    5
    输出样例#1: 复制
    16
    7

    说明

    20%的数据满足:1≤n≤100

    50%的数据满足:1≤n≤6000

    100%的数据满足:1≤n,f≤2*10^5

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