题目描述

给定一个数列Ai(初值为0), 给定若干次操作

1. 选择一个区间全部加上某个值
2. 查询某个区间内的不下降子串数

这里连续的不下降子串记做同一个

例如{1,2,3,4,2,3,3,4,3,4}的答案是3, 分别为{1,2,3,4},{2,3,3,4},{3,4}

而{4,3,2,1}的答案是4, 分别为{4},{3},{2},{1}

输入描述

第一行两个整数$n,m$表示数列长度和操作次数

接下来m行每行一个操作$o,l,r(,v)$

如果o为1, 则表示在[l,r]区间的每个数被加上了v

如果o为2, 则表示查询[l,r]区间的不下降子串数

输出描述

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

样例输入：

6 6
1 2 3 1
1 4 5 -1
2 1 6
2 1 4
2 1 3
2 4 6

样例输出：

2
2
1
1

数据范围

保证 $ 0 < n,m <= 100000, 1 <= l<=r <= n, |v|<=10^9 $

子任务1:(100分)

无其他限制

题目来源

zdw1999