[Ynoi2004] rpfrdtzls
题目描述
给定 $n,m,A$,维护由序列构成的序列 $a_1,\dots,a_n$,初始 $a_i$ 包含一个元素 $A+1$;
共 $m$ 次操作:
修改操作:给定 $l,r,x$,对 $l\le i\le r$,在序列 $a_i$ 前面插入元素 $x$
查询操作:给定 $l,r$,查询 $\sum\limits_{i=l}^r F(a_i,A)$
其中 $F((x_1,\dots,x_n),0)=0$
对 $k>0$,$F((x_1,\dots,x_n),k)=F((x_2,\dots,x_n),\lfloor \frac{k}{x_1} \rfloor)+1$
###
输入输出格式
输入格式
第一行三个整数 $n,m,A$;
接下来 $m$ 行,每行 $1,l,r,x$ 表示一个修改操作,或 $2,l,r$ 表示一个查询操作;
输出格式
对每个查询操作,输出一行,表示答案。
输入输出样例
输入样例 #1
5 20 10
1 4 4 166348285
2 2 5
2 1 5
1 1 2 10
1 4 4 3
1 4 5 6
2 5 5
1 5 5 1
1 2 3 1
2 5 5
2 5 5
2 3 4
2 3 3
2 4 5
2 4 4
1 2 5 5
1 5 5 9
1 1 4 5
2 5 5
2 1 4
输出样例 #1
4
5
2
3
3
4
2
5
2
2
8
说明
Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078
对于 $100\%$ 的数据,满足 $1\le n,m\le 5\times 10^5$,$1\le A,x\le 10^9$,$1\le l\le r\le n$。
对于 $25\%$ 的数据,满足 $n,m\le 100$。
对于 $50\%$ 的数据,满足 $n,m\le 10^5$。
对于另外 $25\%$ 的数据,满足 $x\ne 1$。
对于另外 $25\%$ 的数据,无特殊限制。