脚本宝典收集整理的这篇文章主要介绍了CF803G Periodic RMQ Problem 口胡，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
CF803G Periodic RMQ Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给你一个序列 (a) 让你支持
11 ll rr xx 区间赋值
22 ll rr 询问区间最小值
我们觉得这个问题太水了,所以我们不会给你序列aa
而是给你序列一个长度为nn 的序列bb ,把bb 复制粘贴kk 次就可以得到aa
nle105,kle104,qle105,b_ile109n≤105,k≤104,q≤105,b**i≤109
1le lle rle ntimes k1≤l≤r≤n×k
思路1 使用动态开点线段树，每次询问的时候，对于中间块，再开一个线段树维护，复杂度 (O(q(log n+log k)))
思路2 发现如果初值都是 (0) 的话，可以直接裸动态开点，问题在于新开点的时候不知道初值，不妨使用 ST 表，每次开点的时候容易计算出初值
思路3 考虑把询问离线，设离散化后数组 (tmp) ，那么 ([tmp[i-1]+1,tmp[i]]) 这个区间可以看作是一个点，再使用线段树维护即可
以上是脚本宝典为你收集整理的CF803G Periodic RMQ Problem 口胡全部内容，希望文章能够帮你解决CF803G Periodic RMQ Problem 口胡所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。