QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+11]

# 8229. 栈

Statistics

n 个栈,编号为 1n。还有 m 次操作,操作有三种:

  • 1 l r x y,表示给编号在区间 [l,r] 内的栈都压入 xy
  • 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] 内的栈都压入 xy
  • 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

子任务

对于全部的数据满足,1n,m105,1x,y105,1w1010,1pq1010

  • Subtask1(18pts): n,m5000
  • Subtask2(21pts): 保证不存在 2 操作。
  • Subtask3(16pts): 对于所有的操作 1,保证 y=1
  • Subtask4(24pts): 对于所有的 3 操作,保证 p=1,q=1010
  • Subtask5(21pts): 无特殊限制。