Statement
CF803G Periodic RMQ Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给你一个序列 \(a\) 让你支持
11 ll rr xx 区间赋值
22 ll rr 询问区间最小值
我们觉得这个问题太水了,所以我们不会给你序列aa
而是给你序列一个长度为nn 的序列bb ,把bb 复制粘贴kk 次就可以得到aa
n\le105,k\le104,q\le105,b_i\le109n≤105,k≤104,q≤105,b**i≤109
1\le l\le r\le n\times k1≤l≤r≤n×k
Solution
思路1 使用动态开点线段树，每次询问的时候，对于中间块，再开一个线段树维护，复杂度 \(O(q(\log n+\log k))\)
思路2 发现如果初值都是 \(0\) 的话，可以直接裸动态开点，问题在于新开点的时候不知道初值，不妨使用 ST 表，每次开点的时候容易计算出初值
思路3 考虑把询问离线，设离散化后数组 \(tmp\) ，那么 \([tmp[i-1]+1,tmp[i]]\) 这个区间可以看作是一个点，再使用线段树维护即可