U419412 [PKUWC2024] 栈

北京大学信息学冬季体验营 2024 Day 2 T3

有 $n$ 个栈，编号为 $1$ 到 $n$。还有 $m$ 次操作，操作有三种： - `1 l r x y`：表示给编号在区间 $[l,r]$ 内的栈都压入 $x$ 个 $y$。 - `2 l r w`：表示让编号在区间 $[l,r]$ 内的栈执行弹栈操作 $w$ 次，这里弹栈操作是指，如果栈为空，则什么都不做；否则弹出栈顶。 - `3 k p q`：表示查询编号为 $k$ 的栈里从栈底开始数第 $p$ 个到第 $q$ 个元素之和，如果栈不存在第 $i$ 个元素，则视为栈的第 $i$ 个元素为 $0$。

第一行两个整数 $n,m$。 接下来 $m$ 行每行描述了一次操作，形如： - `1 l r x y`：给编号在区间 $[l,r]$ 内的栈都压入 $x$ 个 $y$。 - `2 l r w`：让编号在区间 $[l,r]$ 内的栈执行弹栈操作 $w$ 次。 - `3 k p q`：查询编号为 $k$ 的栈里从栈底开始数第 $p$ 个到第 $q$ 个元素之和。

对于每个询问，输出一个数表示答案。

**本题采用捆绑测试。** 对于全部的数据满足，$1\leq n,m\leq 10^5$，$1\leq x,y\leq 10^5$，$1\leq w\leq 10^{10}$，$1\leq p\leq q\leq 10^{10}$。 子任务 1（$18$ 分）：$n,m\leq 5000$。 子任务 2（$21$ 分）：保证不存在 $2$ 操作。 子任务 3（$16$ 分）：对于所有的操作 $1$，保证 $y=1$。 子任务 4（$24$ 分）：对于所有的 $3$ 操作，保证 $p=1$，$q=10^{10}$。 子任务 5（$21$ 分）：无特殊限制。