[Ynoi2014] 置身天上之森

题目背景

![](https://cdn.luogu.com.cn/upload/pic/45593.png) 如果,我是说如果 我再过五天就会死掉的话 你可以再温柔的对待我一点吗? ![](https://cdn.luogu.com.cn/upload/pic/45555.png) 运气真好 牺牲我一个就可以了 怎么样,就是这么一回事 ![](https://cdn.luogu.com.cn/upload/pic/45566.png) 你现在愿意答应我最后的愿望吗? 那个...就是...比如说...对了 ![](https://cdn.luogu.com.cn/upload/pic/45577.png) 让你吻我之类的 你愿意吗 ![](https://cdn.luogu.com.cn/upload/pic/45586.png) 在自己消失之前 心怀不想消失的愿望 希望让某个人记住我 希望能留下羁绊 我这么希望着,又有什么不可以的吗 ![](https://cdn.luogu.com.cn/upload/pic/45501.png)

题目描述

线段树是一种特殊的二叉树,满足以下性质: 每个点和一个区间对应,且有一个整数权值; 根节点对应的区间是 $[1,n]$; 如果一个点对应的区间是 $[l,r]$,且 $l<r$,那么它的左孩子和右孩子分别对应区间 $[l,m]$ 和 $[m+1,r]$,其中 $m=\lfloor\frac{l+r}{2}\rfloor$; 如果一个点对应的区间是 $[l,r]$,且 $l=r$,那么这个点是叶子; 如果一个点不是叶子,那么它的权值等于左孩子和右孩子的权值之和。 珂朵莉需要维护一棵线段树,叶子的权值初始为 $0$,接下来会进行 $m$ 次操作: 操作 $1$:给出 $l,r,a$,对每个 $x$($l\leq x\leq r$),将 $[x,x]$ 对应的叶子的权值加上 $a$,非叶节点的权值相应变化; 操作 $2$:给出 $l,r,a$,询问有多少个线段树上的点,满足这个点对应的区间被 $[l,r]$ 包含,且权值小于等于 $a$。

输入输出格式

输入格式


第一行两个整数 $n,m$。 接下来 $m$ 行,每行包含四个整数 $op,l,r,a$,表示一次操作,其中 $op$ 表示操作类型。

输出格式


对每个 $op=2$ 的操作,输出一行,包含一个整数,表示答案

输入输出样例

输入样例 #1

3 3
1 2 3 9
2 1 2 1
2 1 3 1

输出样例 #1

1
1

说明

Idea:zcysky, Solution:nzhtl1477( $O( m\sqrt{n\log n})$ solution ),ccz181078( $O( m\sqrt{n})$ solution ) Code:nzhtl1477( $O( m\sqrt{n} \log n)$ code ),ccz181078( $O( m\sqrt{n\log n})$ code ), Data:nzhtl1477 对于 $100\%$ 的数据,$1\leq n,m\leq 10^5$,$1\leq l\leq r\leq n$,$1\leq op\leq 2$,$-10^5\leq a\leq 10^5$。