Problem C. Segtree Master

时间限制：5s

空间限制：256MB

题目描述

对于数组 \(a_1,a_2...a_n\)，请维护一种数据结构：

• 区间修改：给定 \(l,r, v\) ，对于\(a_l,a_{l+1}...a_r\) 中的每一个 \(a_i\)，令 \(a_i\leftarrow \lfloor \frac{a_i}{v}\rfloor\) ，即除以 \(v\) 并向下取整。
• 单点修改：给定 \(x,v\)，请令 \(a_x=v\)
• 单点查询：给定 \(x\)，请返回 \(a_x\) 的值。

输入格式

第一行两个整数 \(n, q\)，表示数组的长度和操作的次数。

接下来一行 \(n\) 个整数，表示这个数组。

接下来 \(q\) 行，每行若干整数。其中第一个整数是操作类型 \(op\)

• 若 \(op=1\)，表示一次区间修改操作，接下来还有三个整数 \(l,r,v\)
• 若 \(op=2\)，表示一次单点修改操作，接下来还有两个整数 \(x,v\)
• 若 \(op=3\)，表示一次单点查询操作，接下来还有一个整数 \(x\)

输出格式

对于每一次操作 \(3\)，输出一行表示答案。

样例输入1

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

样例输出1

4
1
3

样例输入2

4 20
69 52 16 56 
1 2 2 3
2 1 47
2 4 96
3 3
3 1
3 2
3 1
2 4 8
1 2 2 1
1 2 4 2
3 1
1 2 4 3
3 4
3 4
2 2 29
2 1 84
2 1 90
1 1 4 2
2 4 5
3 4

样例输出2

16
47
17
47
47
1
1
5

数据范围

\(2\le n,q\le 3*10^5,1\le l\le r\le n,op\in\{1,2,3\},1\le x\le n,1\le v\le 10^9, 0\le a_i\le 2^{31}-1\)