主页
Featured image of post ACM学习笔记——离线……

ACM学习笔记——离线……

杂项——离线算法……

文章字数:272
预计阅读时长: 分钟

该笔记还未完成整理,待日后继续整理……

离线和在线区别

指的是对于若干个询问操作的不同处理方式。

在线

得到一次询问,便回答一次。

离线

得到所有询问后,再统一回答。

强制在线

离线算法一般都会对询问用id标记,然后进行排序操作,
因此会打乱原本的询问顺序。

e.g.

对于五个询问$1,2,3,4,5$,
离线算法可能按$3,1,4,5,2$的顺序进行计算,最后再统一回答询问。

因此如果要求:某次询问与之前的询问有复合操作(比如xor上次的询问),
便使得不能读完所有操作,计算完后再统一回答,
而只能读一个,计算一个,回答一个。

这便是强制在线。

离线算法