思路:
这题是带修莫队的模板题
实际上带修莫队的操作和普通莫队大致相同,区别在于带修莫队多了一个“时间轴”。
首先将修改与查询分开记录。每个查询记录一个值表示查询前有多少次修改(即“时间”)。处理查询时通过“时间”来决定修改或撤销修改。
根据计算,块大小为$\sqrt[3]{nt}$时可达最优的时间复杂度$O(\sqrt[3]{n^4t})$,其中$t$为修改次数,需要注意$t=0$的情况。
代码:
1 |
|
这题是带修莫队的模板题
实际上带修莫队的操作和普通莫队大致相同,区别在于带修莫队多了一个“时间轴”。
首先将修改与查询分开记录。每个查询记录一个值表示查询前有多少次修改(即“时间”)。处理查询时通过“时间”来决定修改或撤销修改。
根据计算,块大小为$\sqrt[3]{nt}$时可达最优的时间复杂度$O(\sqrt[3]{n^4t})$,其中$t$为修改次数,需要注意$t=0$的情况。
1 | #include <cmath> |