[ACM] 在线 离线 强制在线 | 您所在的位置:网站首页 › 在线离线实时的含义是什么 › [ACM] 在线 离线 强制在线 |
博客背景
OI/ACM中,在做区间查询,区间修改等问题的时候,经常会听到各位大佬说到“离线”、“在线”等令我一脸懵逼的名词,所以决定要搞懂是什么意思。 博客正文一.简单的理解 在线和离线可以简单的理解为对于所有的操作是否需要读入完毕。 二.标准理解和要求 在线的要求是可以不用先知道所有的操作(类似询问、修改),边读入边执行,类似“走一步,做一步”的思想。 离线则与在线相反,要求必须知道所有的操作,类似"记录所有步,回头再做”的思想,一般用Query[ ]记录所有操作。 三.常见的算法 常见的在线算法:带有“可持久化”字样的(主席树、可持久化线段树、可持久化字典树等等),其实正常写题时基本上都是在线的思路。 常见的离线算法:整体二分、CDQ分治、莫队算法。 四.应用 对于正常的题目来讲,两种算法其实都可以使用,经典的题目如:动态第K大问题(ZOJ2112),解法有树套树(在线)和整体二分/CDQ分治(离线),但是区别在于: 在线算法的思路相对简单,而代码量大(如某些毒瘤题),容易爆栈,赛场上及其考验心态。 离线算法的思路相对复杂,而代码量小,建议选手多采用(毕竟代码越多,DEBUG越困难)。 五.强制在线 对于一些不正常的题目(强制在线),只能老老实实码数据结构了。 强制在线的例子如:当前读入的数据需要xor上一次的结果、交互式等。 |
CopyRight 2018-2019 实验室设备网 版权所有 |