注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "weirdtree.h"。

题目描述

题目译自 Romanian Master of Informatics 2021 Day2 T3 「Weirdtree」

高地女巫阿兹莎发现了一个充满古怪树木的花园！因此，她和她的朋友莱卡决定在那里度过一些时间照顾花园。

花园可以看作是一系列 $N$ 棵树，其中树木的编号为 $1$ 到 $N$ 。每棵树都有一个特定的非负整数高度。然后，阿兹莎将根据一个包含 $Q$ 个条目的日程表来度过她的时间，这些条目可以是几种类型：

1. 树木切割阶段，由三个整数 $l, r, k$ 表示。在这个阶段，阿兹莎将在接下来的 $k$ 天内切割树木。每天她都会找到编号在 $l$ 和 $r$ 之间最高的树，并将其高度减少 $1$。如果有多棵树具有这种最大高度，她会选择最左边的树。如果最高的树的高度为 $0$，则当天不会发生任何事情。
2. 魔法阶段，由两个整数 $i$ 和 $x$ 表示。在这个阶段，阿兹莎会改变编号为 $i$ 的树的高度为 $x$。
3. 树木询问阶段，由两个整数 $l$ 和 $r$ 表示。在这个阶段，阿兹莎将找到编号在 $l$ 和 $r$ 之间（包含 $l$ 和 $r$）的树的高度之和。

阿兹莎好奇树木询问阶段的结果是什么，并希望在不经历整个日程表的情况下知道它们。你能帮她吗？

实现细节

你必须实现以下四个函数：

void initialise(int N, int Q, int h[]);
void cut(int l, int r, int k);
void magic(int i, int x);
long long int inspect(int l, int r);

initialise 函数给定 $N$（树的数量）、$Q$（日程表中的条目数）和一个数组 $h$，其中 $h[i]$ 是树 $i\ (1\leq i\leq N)$ 的高度。这个函数在会调用其他三个函数之前调用一次。cut、magic 和 inspect 函数分别代表树切割、魔法和树询问阶段，并由它们各自的参数表示。你的 inspect 函数实现必须返回编号在 $l$ 和 $r$ 之间的树的高度之和。

你不应实现 main 函数。您将在「文件」中获得一个交互器示例 grader.cpp。我们的 main 函数将读取 $N, Q$、$N$ 个初始高度的序列和 $Q$ 个日程表条目。三种类型的日程表条目（cut(l, r, k)、magic(i, x) 和 inspect(l, r)）的格式分别为 1 l r k、2 i x 和 3 l r。这也是样例中使用的输入格式。

6 10
1 2 3 1 2 3
1 1 6 3
3 1 6
1 1 3 3
3 1 6
1 1 3 1000
3 1 6
2 1 1000
3 1 6
1 1 3 999
3 1 5

9
6
5
1005
4

在第一阶段，经过 $3$ 天的树木切割后，树木的高度为 $1,2,2,1,2,3$；$1,2,2,1,2,2$；和 $1,1,2,1,2,2$。这些值的总和是 $9$，这是第二阶段询问的答案。

在第三阶段，经过 $3$ 天的树木切割后，树木的高度为 $1,1,1,1,2,2$；$0,1,1,1,2,2$；和 $0,0,1,1,2,2$。这些值的总和是 $6$，这是第四阶段询问的答案。

在第五阶段，经过 $1000$ 天的树木切割后，树木的高度为 $0,0,0,1,2,2$。这是因为高度为 $0$ 的树无法被切割。这些值的总和是 $5$，这是第六阶段询问的答案。

在第七阶段，第一棵树的高度变为 $1000$，树木的高度为 $1000,0,0,1,2,2$。这些值的总和是 $1005$，这是第八阶段询问的答案。

在第九阶段，每一天的树木切割都会将第一棵树的高度减少 $1$。这在我们阶段结束时给了我们树高 $1,0,0,1,2,2$。前五个值的总和是 $4$，这是第十个也是最后一个阶段询问的答案。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, Q \leq 3\cdot 10^5$
• 保证 cut、magic 和 inspect 函数总共将被调用 $Q$ 次。
• $1 \leq i \leq N$
• $0 \leq x, k, h[i] \leq 10^9$
• $1 \leq l \leq r \leq N$

详细子任务附加限制及分值如下表所示。