2020-2021:teams:manespace:莫队
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:莫队 [2020/05/09 20:50] iuiou [莫队] |
2020-2021:teams:manespace:莫队 [2020/05/10 21:24] (当前版本) iuiou |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ==== 简介 ==== | ==== 简介 ==== | ||
| - | 严格来说，莫队只是一种对暴力做法的优化，主要用于维护区间答案或者维护区间上的数据结构。可以被拓展为带修改莫队，树上莫队，树上带修改莫队等。 | + | 严格来说，莫队只是一种对暴力做法的优化，主要用于维护区间答案或者维护区间上的数据结构。可以被拓展为带修改莫队，树上莫队，树上带修改莫队等。(这些有时间说，先咕咕咕) |
| ==== 那它能干啥 ==== | ==== 那它能干啥 ==== | ||
| 行 25: | 行 25: | ||
| **优化1**：对于每个区间从区间头开始扫，与到没遇见的ans++，标记一下，然后继续往下扫到查询区间结束。这样我们成功把复杂度降低到了O(nm) | **优化1**：对于每个区间从区间头开始扫，与到没遇见的ans++，标记一下，然后继续往下扫到查询区间结束。这样我们成功把复杂度降低到了O(nm) | ||
| - | **优化2**：还是开一个cnt数组，用两个指针i，j在数列上移动，来缩减目标范围，遇到一个数j，如果cnt[j]为0，则ans++，当要缩减区间范围时若cnt[j]正好为1，则ans--，由于每次接着上次操作的结果，只要对cnt数组进行操作。复杂度的到一定的优化，然而，对于查询区间为[1,n][1,n-1][1,n-2]……这样和重新扫没区别，复杂度依旧还是O(nm)，一样爆炸…… | + | **优化2**：还是开一个cnt数组，用两个指针i，j在数列上移动，来缩减目标范围，遇到一个数j，如果cnt[j]为0，则ans++，当要缩减区间范围时若cnt[j]正好为1，则ans--，由于每次接着上次操作的结果，只要对cnt数组进行操作。复杂度的到一定的优化，然而，对于查询区间为[1,n][1,2][3,n]……这样和重新扫没区别，复杂度依旧还是O(nm)，一样爆炸…… |
| 简要放个代码描述一下处理过程 | 简要放个代码描述一下处理过程 | ||
| 行 122: | 行 122: | ||
| </code> | </code> | ||
| + | 最后挂一个巨佬写的莫队博客，很清楚，可以参考[[https://www.cnblogs.com/WAMonster/p/10118934.html]] | ||
2020-2021/teams/manespace/莫队.1589028620.txt.gz · 最后更改: 2020/05/09 20:50 由 iuiou
