P17131 [ICPC 2025 Shanghai R] No more regrets

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

省队选拔结束后，White 陷入了长时间的消沉。她在成绩中看不到任何希望。即便如此，White 仍在坚持 NOI 前的最后一段训练。除了常规训练，她开始涉足自己 OI 生涯中从未有机会学习的专题——希望在告别之前，不再留下遗憾。 甩开纷乱的思绪，White 突然聚焦在眼前的一道题上，一道朴素而枯燥的数据结构题—— White 有一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$。她将对该序列执行 $q$ 次操作。每次操作是以下三种类型之一： - $1\ l\ r\ v$ — 将区间 $[l, r]$ 中的每个元素加上 $v$。 - $2\ l\ r\ v$ — 将区间 $[l, r]$ 中的每个元素赋值为 $v$。 - $3\ l\ r$ — 查询 $\sum_{i=l}^{r}(\min_{j=l}^{i} a_j) \times (\max_{j=l}^{i} a_j)$ 的值，结果对 $2^{64}$ 取模。 你的任务是模拟所有操作，并输出所有查询的结果。

第一行包含 $2$ 个整数 $n, q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示元素个数和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$)，表示初始的元素。 接下来的 $q$ 行，每行描述一次操作，格式为以下三种之一： - $1\ l\ r\ v$ ($1 \le l \le r \le n$，$-10^9 \le v \le 10^9$)，表示区间加操作。 - $2\ l\ r\ v$ ($1 \le l \le r \le n$，$1 \le v \le 10^9$)，表示区间赋值操作。 - $3\ l\ r$ ($1 \le l \le r \le n$)，表示查询操作。 保证在整个过程中，对于每个 $1 \le i \le n$ 都有 $0 \le a_i \le 10^9$。

对于每个查询操作，输出一行一个整数——查询结果对 $2^{64}$ 取模的值。

对于第 $1$ 个测试用例： 初始序列为 $2\ 3\ 5\ 4\ 1$。经过第 $3$ 次操作后变为 $2\ 3\ 2\ 2\ 1$，经过第 $6$ 次操作后变为 $7\ 8\ 7\ 7\ 6$。 对于第 $1$ 个查询，答案为 $\sum_{i=1}^{5}(\min_{j=1}^{i} a_j) \times (\max_{j=1}^{i} a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$。 对于第 $2$ 个查询，答案为 $\sum_{i=2}^{4}(\min_{j=2}^{i} a_j) \times (\max_{j=2}^{i} a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$。 翻译由 DeepSeek V4 Pro 完成