QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 8229. 栈

统计

有 $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$ 个元素之和。

输出格式

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

样例数据

样例输入

4 8
1 1 3 3 2
1 2 4 2 1
3 1 2 4
3 2 2 4
2 2 3 1
2 1 2 2
3 1 1 1
3 2 2 3

样例输出

4
5
2
2

子任务

对于全部的数据满足,$1\le n,m\le 10^5,1\le x,y\le 10^5,1\le w\le 10^{10},1\le p\le q\le 10^{10}$。

  • Subtask1(18pts): $n,m\le 5000$。
  • Subtask2(21pts): 保证不存在 $2$ 操作。
  • Subtask3(16pts): 对于所有的操作 $1$,保证 $y=1$。
  • Subtask4(24pts): 对于所有的 $3$ 操作,保证 $p=1,q=10^{10}$。
  • Subtask5(21pts): 无特殊限制。