2020-2021:teams:manespace:莫队
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:莫队 [2020/05/10 21:23] iuiou |
2020-2021:teams:manespace:莫队 [2020/05/10 21:24] (当前版本) iuiou |
||
|---|---|---|---|
| 行 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][n-2,1][3,n]……这样和重新扫没区别，复杂度依旧还是O(nm)，一样爆炸…… | + | **优化2**：还是开一个cnt数组，用两个指针i，j在数列上移动，来缩减目标范围，遇到一个数j，如果cnt[j]为0，则ans++，当要缩减区间范围时若cnt[j]正好为1，则ans--，由于每次接着上次操作的结果，只要对cnt数组进行操作。复杂度的到一定的优化，然而，对于查询区间为[1,n][1,2][3,n]……这样和重新扫没区别，复杂度依旧还是O(nm)，一样爆炸…… |
| 简要放个代码描述一下处理过程 | 简要放个代码描述一下处理过程 | ||
2020-2021/teams/manespace/莫队.1589117012.txt.gz · 最后更改: 2020/05/10 21:23 由 iuiou
