1.前言
没有前言。
2.例题
2.1 CF438D
有一个长度为 \(n\) 的数列 \(\{a_n\}\) 和 \(m\) 次操作，操作内容如下：
- 格式为
1 l r，表示求 \(\sum \limits _{i=l}^{r} a_i\) 的值并输出。- 格式为
2 l r x，表示对区间 \([l,r]\) 内每个数取模，模数为 \(x\)。- 格式为
3 k x，表示将 \(a_k\) 修改为 \(x\)。
操作一与操作三显然好做。
操作二并不好做，如果下传标记，不好合并，所以我们可以暴力取模。若一个区间内的最大值小于模数，那么这个区间不用执行取模操作：\(x\ mod\ y = x\ \ (x < y)\)。若这个区间内的最大值大于等于模数时，我们才进行取模操作。
取模具有一个性质：\(x\ mod\ y < \frac{x}{2}\ \ (x \ge y)\)。
证明：
设 \(x = k\cdot y + b\)，其中 \(x,k,y,b\) 均为整数，\(b < y\)，\(\lvert k \rvert \ge 1\)。
则 \(x\ mod\ y = b\)。
\(\because b < y\)，\(\lvert k \rvert \ge 1\)
\(\therefore k\cdot y > b\)
\(\therefore b < \frac{x}{2}\)得证。
根据这个性质，我们可以知道，每个数 \(x\)，至多被取模 \(\log_{2}{x}\) 次。
修改一个数字即可视作添加一个数字 \(y\)，我们至多需要多修改 \(\log_{2}{y}\) 次。
所以取模的总复杂度为 \(O((n + m)\log{V})\)。
另外两个操作用脚做就行了。
2.2 LG5787
有一个 \(n\) 个节点的图。
有一些边 \(u\to v\) 会在时刻 \(l\) 出现，在时刻 \(r\) 消失。
求在每一时刻，该图是否为二分图。