Ex - I like Query Problem Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N, Q および A = (a_1, a_2, \dots, a_N) が与えられます。
以下で説明されるクエリを Q 個処理してください。クエリは次の 3 種類のいずれかです。

  • 1 L R x : i=L,L+1,\dots,R について a_i の値を \displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor に更新する。
  • 2 L R y : i=L,L+1,\dots,R について a_i の値を y に更新する。
  • 3 L R : \displaystyle\sum_{i=L}^R a_i を出力する。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq L \leq R \leq N
  • 1 \leq a_i \leq 10^5
  • 2 \leq x \leq 10^5
  • 1 \leq y \leq 10^5
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで\text{query}_i は i 番目に処理するクエリである。

N Q
a_1 a_2 \dots a_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下の 3 種類のいずれかの形式で与えられる。

1 L R x

2 L R y

3 L R

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

出力例 1

13
4
9

はじめ、A = (2, 5, 6) です。よって 1 番目のクエリの答えは a_1 + a_2 + a_3 = 2 + 5 + 6 = 13 になります。
2 番目のクエリを処理した直後は A = (2, 2, 3) です。よって 3 番目のクエリの答えは a_1 + a_2 = 2 + 2 = 4 になります。
4 番目のクエリを処理した直後は A = (3, 3, 3) です。よって 5 番目のクエリの答えは a_1 + a_2 + a_3 = 3 + 3 + 3 = 9 になります。

入力例 2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

出力例 2

51
12
33
26
132

Score : 600 points

Problem Statement

You are given N, Q, and A=(a_1,\ldots,a_N).
Process Q queries described below. Each query is of one of the following three kinds:

  • 1 L R x: for i=L,L+1,\dots,R, update the value of a_i to \displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor.
  • 2 L R y: for i=L,L+1,\dots,R, update the value of a_i to y.
  • 3 L R: print \displaystyle\sum_{i=L}^R a_i.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq L \leq R \leq N
  • 1 \leq a_i \leq 10^5
  • 2 \leq x \leq 10^5
  • 1 \leq y \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format, where \text{query}_i denotes the i-th query to be processed:

N Q
a_1 a_2 \dots a_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in one of the following three formats:

1 L R x

2 L R y

3 L R

Output

Print the answer to the queries as specified in the Problem Statement, with newlines in between.

Sample Input 1

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

Sample Output 1

13
4
9

Initially, A = (2, 5, 6). Thus, the answer to the 1-st query is a_1 + a_2 + a_3 = 2 + 5 + 6 = 13.
When the 2-nd query has been processed, A = (2, 2, 3). Thus, the answer to the 3-rd query is a_1 + a_2 = 2 + 2 = 4.
When the 4-th query has been processed, A = (3, 3, 3). Thus, the answer to the 5-th query is a_1 + a_2 + a_3 = 3 + 3 + 3 = 9.

Sample Input 2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

Sample Output 2

51
12
33
26
132