该笔记还未完成整理,待日后继续整理……
离线和在线区别
指的是对于若干个询问操作的不同处理方式。
在线
得到一次询问,便回答一次。
离线
得到所有询问后,再统一回答。
强制在线
离线算法一般都会对询问用id
标记,然后进行排序操作,
因此会打乱原本的询问顺序。
e.g.
对于五个询问$1,2,3,4,5$,
离线算法可能按$3,1,4,5,2$的顺序进行计算,最后再统一回答询问。
因此如果要求:某次询问与之前的询问有复合操作(比如xor
上次的询问),
便使得不能读完所有操作,计算完后再统一回答,
而只能读一个,计算一个,回答一个。
这便是强制在线。
离线算法
- CDQ 分治
- 整体二分
- 莫队算法