在 R42645505(下称 05 版)和 R42648036(下称 36 版)中分别有这题带修莫队的两个实现,有以下区别:
- 05 版在数组中记录的是颜色,然后每次开桶来统计颜色个数;而 36 版在数组中记录的是指向桶内对应元素的指针。R42648841(41 版)是只包含这一区别的提交记录。
- 对于每个修改操作,05 版记录了每次修改的位置,而 36 版记录的是一个指针指向每次修改的数组元素。
- 对于每个询问操作,05 版记录了对应的答案写入的数组下标,而 36 版记录的是对应的指针。
- 还有其他一些类似区别。
简单来说就是 05 版里面中所有需要用到数组的地方都在 36 版中由记录数组下标改成了记录指针。(除了在循环里面循环变量兼任下标职能。)
按照我以前学习的知识,一次数组访问包括一次 long long 加法和一次解引用,而记录指针的话只需要一次解引用,那么 36 版或者是 41 版应该快于 05 版,但是结果却是 36 版速度与 41 版差不多,比 05 版慢了近 0.5s(各个测试点总时间,2.90s->3.50s)。
所以为什么会慢啊(蹲一个大佬)。