CF803G Periodic RMQ Problem
题目描述
给定一个长度为 n 的整数序列 b={b1,b2,…,bn}。将 b 复制 k 份并依次拼接,得到一个长度为 n×k 的序列 a。也就是说,对于每个 1≦i≦n×k,都有 ai=b((i−1)modn)+1。
你需要对序列 a 依次执行 q 次操作,每次操作是以下两种类型之一:
∙类型 1:给定 l,r,x,将 al,al+1,…,ar 全部赋值为 x;
∙类型 2:给定 l,r,求 al,al+1,…,ar 中的最小值。
输入格式
第一行输入两个整数 $n,k\left(1 \leqq n \leqq 10^5;\ 1 \leqq k \leqq 10^4\right)$ 代表序列 b 的长度与复制次数。序列 a 的长度为 n×k。
第二行输入 n 个整数 $b_1,b_2,\dots,b_n\left(1 \leqq b_i \leqq 10^9\right)$ 代表序列 b 中的元素。
第三行输入一个整数 q(1≦q≦105) 代表操作次数。
此后 q 行,每行先输入一个整数 t(1≦t≦2) 代表操作类型,编号同题干。随后在同一行:
∙若 t=1,输入三个整数 $l,r,x\left(1 \leqq l \leqq r \leqq n \times k;\ 1 \leqq x \leqq 10^9\right)$ 代表赋值操作的区间与赋值;
∙若 t=2,输入两个整数 l,r(1≦l≦r≦n×k) 代表查询最小值的区间。
所有操作的下标都基于序列 a 的下标,即下标的取值范围是 [1,n×k]。
输出格式
对于每次类型 2 的操作,新起一行输出一个整数,代表该次查询的区间最小值。
测试样例
3 1
1 2 3
3
2 1 3
1 1 2 4
2 1 3
1
3
样例 1 解释
此时 k=1,序列 a=b={1,2,3},各次操作如下:
∙查询区间 [1,3] 的最小值,得到 min{1,2,3}=1;
∙将区间 [1,2] 赋值为 4,序列变为 {4,4,3};
∙查询区间 [1,3] 的最小值,得到 min{4,4,3}=3。
3 2
1 2 3
5
2 4 4
1 4 4 5
2 4 4
1 1 6 1
2 6 6
1
5
1