T240056 [PKUSC2021 D1T2] 逛街

给定长度为 $n$ 的序列 $a_i$，$Q$ 次操作。 - `1 l r`：$\forall l \leq i < r, a_i = \max\{a'_i, a'_{i+1}\}$，其中 $a'_i$ 为未修改前 $a_i$ 的权值。 - `2 l r`：求出 $\sum_{x\in S}a_x$，其中 $S = \{x|l \leq x \leq r, \forall l \leq i < x, a_i < a_x\}$。

第一行$n$,$Q$ 第二行$n$个整数$a_i$ 接下来$Q$行每行都是一个操作

对于每个询问输出答案

$1 \leq n, Q \leq 3 \times 10^5, 1 \leq a_i \leq 10^9$,。 Subtask1(7pts)：$n,Q\leq 3000$ Subtask2(39pts)：对于所有1操作，$l=1,r=n$ Subtask3(54pts)：无特殊限制