#CF803G. 循环数组区间最小值

循环数组区间最小值

CF803G Periodic RMQ Problem

题目描述

\hspace{15pt}给定一个长度为 nn 的整数序列 b={b1,b2,…,bn}b=\{b_1,b_2,\dots,b_n\}。将 bb 复制 kk 份并依次拼接,得到一个长度为 n×kn \times k 的序列 aa。也就是说,对于每个 1≦i≦n×k1 \leqq i \leqq n \times k,都有 ai=b((i−1) mod n)+1a_i=b_{\left(\left(i-1\right) \bmod n\right)+1}。

\hspace{15pt}你需要对序列 aa 依次执行 qq 次操作,每次操作是以下两种类型之一:

∙ \hspace{23pt}\bullet\,类型 11:给定 l,r,xl,r,x,将 al,al+1,…,ara_l,a_{l+1},\dots,a_r 全部赋值为 xx;

∙ \hspace{23pt}\bullet\,类型 22:给定 l,rl,r,求 al,al+1,…,ara_l,a_{l+1},\dots,a_r 中的最小值。

输入格式

\hspace{15pt}第一行输入两个整数 $n,k\left(1 \leqq n \leqq 10^5;\ 1 \leqq k \leqq 10^4\right)$ 代表序列 bb 的长度与复制次数。序列 aa 的长度为 n×kn \times k。

\hspace{15pt}第二行输入 nn 个整数 $b_1,b_2,\dots,b_n\left(1 \leqq b_i \leqq 10^9\right)$ 代表序列 bb 中的元素。

\hspace{15pt}第三行输入一个整数 q(1≦q≦105)q\left(1 \leqq q \leqq 10^5\right) 代表操作次数。

\hspace{15pt}此后 qq 行,每行先输入一个整数 t(1≦t≦2)t\left(1 \leqq t \leqq 2\right) 代表操作类型,编号同题干。随后在同一行:

∙ \hspace{23pt}\bullet\,若 t=1t=1,输入三个整数 $l,r,x\left(1 \leqq l \leqq r \leqq n \times k;\ 1 \leqq x \leqq 10^9\right)$ 代表赋值操作的区间与赋值;

∙ \hspace{23pt}\bullet\,若 t=2t=2,输入两个整数 l,r(1≦l≦r≦n×k)l,r\left(1 \leqq l \leqq r \leqq n \times k\right) 代表查询最小值的区间。

\hspace{15pt}所有操作的下标都基于序列 aa 的下标,即下标的取值范围是 [1,n×k]\left[1,n \times k\right]。

输出格式

\hspace{15pt}对于每次类型 22 的操作,新起一行输出一个整数,代表该次查询的区间最小值。

测试样例

3 1
1 2 3
3
2 1 3
1 1 2 4
2 1 3
1
3

样例 1 解释

\hspace{15pt}此时 k=1k=1,序列 a=b={1,2,3}a=b=\{1,2,3\},各次操作如下:

∙ \hspace{23pt}\bullet\,查询区间 [1,3]\left[1,3\right] 的最小值,得到 min⁡{1,2,3}=1\min\{1,2,3\}=1;

∙ \hspace{23pt}\bullet\,将区间 [1,2]\left[1,2\right] 赋值为 44,序列变为 {4,4,3}\{4,4,3\};

∙ \hspace{23pt}\bullet\,查询区间 [1,3]\left[1,3\right] 的最小值,得到 min⁡{4,4,3}=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