E - Range Division and SUM Queries
問題文
長さ $N$ の非負整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます。以下の2種類のクエリを合計 $Q$ 回順番に処理してください。
1 l r x： $A_l,A_{l+1},\cdots,A_r$ を、それぞれ $\displaystyle \left\lfloor \frac{A_l}{x} \right\rfloor,\left\lfloor \frac{A_{l+1}}{x} \right\rfloor,\cdots,\left\lfloor \frac{A_r}{x} \right\rfloor$ に更新する。2 l r： $\displaystyle \sum_{i=l}^r A_i$ を出力する。
ただし、 $\lfloor a \rfloor$ は $a$ 以下の整数のうち最大のものを表します。
制約
- 入力は全て整数
- $1\leq N \leq 10^5$
- $1\leq Q \leq 2\times 10^5$
- $0\leq A_i \leq 10^{9}\quad (1\leq i\leq N)$
- $1\leq l \leq r\leq N$
- $1\leq x \leq 10^{9}$
入力
入力は以下の形式で与えられる。
$N\quad Q$
$A_1\quad A_2\quad \cdots\quad A_N$
$\rm{query_1}$
$\rm{query_2}$
$\vdots$
$\rm{query_Q}$
ここで、$\rm{query_i}$ は $i$ 番目に処理するクエリである。各クエリは以下のいずれかの形式で与えられる。
$1\quad l\quad r\quad x$
$2\quad l\quad r$
出力
問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。
6 6
20 30 14 26 30 2
2 1 3
1 2 6 5
2 1 5
1 2 3 6
1 4 5 4
2 3 6
64
39
2
はじめ、 $A=(20,30,14,26,30,2)$ です。
1番目のクエリについて、 $A$ の1番目から3番目の要素は $20,30,14$ です。 これらの和は $64$ なので。 $64$ を出力します。
2番目のクエリについて、 $A$ の2番目から6番目の要素は $30,14,26,30,2$ です。 これらをそれぞれ $6,2,5,6,0$ に更新します。 更新後の数列は $A=(20,6,2,5,6,0)$ です。
3番目のクエリについて、 $A$ の1番目から5番目の要素は $20,6,2,5,6$ です。 これらの和は $39$ なので、 $39$ を出力します。
4番目のクエリについて、 $A$ の2番目から3番目の要素は $6,2$ です。 これらをそれぞれ $1,0$ に更新します。 更新後の数列は $A=(20,1,0,5,6,0)$ です。
5番目のクエリについて、 $A$ の4番目から5番目の要素は $5,6$ です。 これらをそれぞれ $1,1$ に更新します。 更新後の数列は $A=(20,1,0,1,1,0)$ です。
6番目のクエリについて、 $A$ の3番目から6番目の要素は $0,1,1,0$ です。 これらの和は $2$ なので、 $2$ を出力します。
4 1
2 0 2 5
1 1 4 10
クエリ2が1つも与えられないことがあります。
2 2
1000000000 0
1 1 2 1
2 1 2
1000000000