QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 125 MB Total points: 100

# 7485. 置身天上之森

统计

线段树是一种特殊的二叉树,满足以下性质:

每个点和一个区间对应,且有一个整数权值;

根节点对应的区间是 $[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$ 的操作,输出一行,包含一个整数,表示答案

样例数据

样例输入

3 3
1 2 3 9
2 1 2 1
2 1 3 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$。