1.分块
我们把整个序列割成 \(s\) 个块，则块长为 \(\frac{n}{s}\)，对于一个跨越区间 \([l,r]\) 的修改/询问，很容易看出它最多包含两个散块，然后中间有一堆整块。
考虑对于整块我们类似线段树的维护方法打 tag，然后对于散块 直接暴力。
分析复杂度，最多有 \(s\) 个块，散块暴力大概要 \(\frac{n}{s}\) 次，则总复杂度是 \(O(q\times(s+\frac{n}{s}))\)。
我们把整个序列割成 \(s\) 个块，则块长为 \(\frac{n}{s}\)，对于一个跨越区间 \([l,r]\) 的修改/询问，很容易看出它最多包含两个散块，然后中间有一堆整块。
考虑对于整块我们类似线段树的维护方法打 tag，然后对于散块 直接暴力。
分析复杂度，最多有 \(s\) 个块，散块暴力大概要 \(\frac{n}{s}\) 次，则总复杂度是 \(O(q\times(s+\frac{n}{s}))\)。