#P2357. 守墓人

    ID: 1306 远端评测题 1000ms 128MiB 尝试: 2 已通过: 2 难度: 4 上传者: 标签>线段树树状数组块状链表块状数组分块

守墓人

题目背景

在一个荒凉的墓地上,有一个令人尊敬的守墓人, 他看守的墓地从来没有被盗过, 所以人们很放心的把自己的先人的墓安顿在他那

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

因为……守墓人懂风水 0.0

题目描述

他把墓地分为主要墓碑和次要墓碑, 主要墓碑只能有 11 个, 守墓人把他记为 11 号, 而次要墓碑有 n1n-1 个,守墓人将之编号为 2,3n2,3\dots n,所以构成了一个有 nn 个墓碑的墓地。

而每个墓碑有一个初始的风水值,这些风水值决定了墓地的风水的好坏,所以守墓人需要经常来查询这些墓碑。

善于运用风水的守墓人,通过一次次逆天改命,使得自己拥有了无限寿命,没人知道他活了多久。这天,你幸运的拜访到了他,他要求你和他共同见证接下来几年他的战果,但不过他每次统计风水值之和都需要你来帮他计算,算错了他会要你命 QAQ

风水也不是不可变,除非遭遇特殊情况,已知在接下来的 21474836472147483647 年里,会有 ff 次灾难,守墓人会有几个操作:

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

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

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

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

5.求主墓碑的风水值

上面也说了,很多人会把先人的墓安居在这里,而且守墓人活了很多世纪→_→,墓碑的数量会多的你不敢相信= =

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

为了活命,还是帮他吧

输入格式

第一行,两个正整数 n,fn,f 表示共有 nn 块墓碑,并且在接下来的 21474836472147483647 年里,会有 ff 次世界末日

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

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

输出格式

输出会有若干行,对 4455 的提问做出回答

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
16
7

提示

20%20\% 的数据满足:1n1001\leq n\leq 100

50%50\% 的数据满足:1n60001\leq n\leq 6000

100%100\% 的数据满足:1n,f2×1051\leq n,f\leq 2 \times 10^5,答案不超过 64 位整数。