Problem C. Segtree Master

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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\)

2022年暑期算法队集训赛

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2022-07-08 08:00
结束于
2022-07-09 00:00
持续时间
16.0 小时
主持人
参赛人数
109