Uoj#46. 【清华集训2014】玄学
题意:
- 给定$n$个数,$m$次操作有两种:
- 增加一个操作,将区间$[l,r]$中的数$x$变为$(ax+b) \bmod m$。
- 执行编号区间$[l,r]$内的操作,询问第$k$个数的值。
- $n\le 100000,m\le 600000$。
题解:
- 考虑用线段树维护操作区间。
- 考虑到$len$个操作至多可以将原数列分为$O(len)$段,所以如果采用归并,节点信息的合并就是$O(size)$ 的。
- 对于每个线段树节点,我们只在它完全被加入完毕后进行节点信息的合并(操作数达到其右端点),这样每个节点最多被合并一次,合并复杂度就是$O(m\log m)$。
- 询问的时候对于每个定位到的线段树节点二分查找到所在位置,因为每个节点的断点数是$O(size)$的,所以每次询问的总复杂度还是$O(\log n)$的。
代码:
1 |
|