区间赋值与区间最小值，并且下标可以达到 $10^9$ 。

遇到这种下标很大的情况，往往做法有几种，要么离散化后变成一个下标不大的情况，要么用动态开点线段树，要么用平衡树来维护连续段。

然后可以考虑利用动态开点线段树来维护这个东西。如果初始序列全是 $0$ ，那么这个东西是很好维护的，只需要区间赋值后打上标记，每个节点维护区间中的最小值。

那么在初始区间非 $0$ 的时候是否可以套用这个做法？实际上，如果可以快速查询一个区间的最小值，也就是查询一个区间在主席树节点上应是的值，那么可以用类似的做法，具体而言，在动态开点线段树新增一个点的时候，并不把初始值设置为 $0$ ，而是设置为这个区间在动态开点线段树上应该维护的值。这样这棵动态开点线段树就等价于真正对这个序列建线段树建立出来的东西了。

如何快速查询一个区间 $[l,r]$ 的最小值呢？由于实际序列是原序列进行 $k$ 次复制得到的，如果区间长度不小于 $n$ ，那么区间内的最小值等价于原序列的最小值。否则，情况就分为原序列的一段前缀和一段后缀，以及原序列上的一段区间。这两种都可以通过 $\text{ST}$ 表做到 $O(1)$ 查询，所以在线段树上新开点的复杂度就是 $O(1)$ 。

因此总复杂度就是 $O(q\log(nk) + n\log n)$ 。

这大概是最好写，也是官方题解所给出的做法。但是其实这个题还有很多其他做法，大概参考了一下神仙们的代码，写一下。

首先是一种 Um_nik 的离线做法，其实场上大多数 AC 都是这么写的，感觉也是最好想的一种。

可以考虑离散化来解决这个问题。如果离线下来所有询问，然后离散化一下，这样区间的端点数量就是 $O(q)$ 级别的。然后考虑预处理好所有的端点间的区间，也就是用类似之前所说的快速查询 $[l,r]$ 最小值的方法来进行预处理，然后可以得到一个长度为 $O(q)$ 的序列。这样就可以直接拿线段树来维护整个序列了（也就是一个区间赋值，区间最小值的普通线段树）。

还有一种个人觉得最难想到也最难写的做法（#）。既然原序列每 $n$ 个数是一样的，我们不妨把 $n$ 个数缩成一个块，然后就得到了一个 $k$ 个块的序列。我们考虑对一个块来建一个真正的线段树，然后再用每个块作为叶子节点，建立一个 $k$ 个块的线段树，这里的线段树都是动态开点的。

然后考虑进行修改操作，我们需要在维护块的线段树上定位 $[l,r]$ ，再在 $l,r$ 分别所属的叶子上的线段树来进行修改，会发现每次修改操作在外面的线段树上影响了 $O(\log k)$ 个节点，在里层线段树上影响了 $O(\log n)$ 个节点，而且只有两个里层线段树会受影响，其他里层线段树都是在祖先被打标记的。所以实际上的时间复杂度是 $O(q(\log k + \log n)) = O(q\log(kn))$ 。询问操作类似。这个做法感觉对代码能力和思维能力要求都高于前两个做法了。