11.6第九周总结

        这周看的是和莫队有关的东西。

        最普通的莫队可以求，给出若干询问，每次询问给出一个区间，求这个区间某个元素出现的次数之类的问题。小B的询问 - 洛谷

        不过莫队算法只能离线。莫队用了分块的思想，对于同一块中的询问，将区间右端点从小到大排序，不同块的询问，根据区间左端点排序，从而降低时间复杂度。还有一种奇偶性排序，好像降低的更多。

        带修莫队：[国家集训队] 数颜色 / 维护队列 - 洛谷

        多增加一维时间戳，核心思想是查询操作的时间戳沿用之前的最近修改的时间戳。改少了就改，改多了就再改回来。比较有意思的是这个题在修改的时候用了一个swap操作，这样可以在修改多了之后，方便再改回来。

        树上莫队：COT2 - Count on a tree II - 洛谷

         对于一个欧拉序，若两点之间的数只出现一次，那么这些数就组成了这两点之间的路径。对于判断是否只出现一次，异或操作可以很方便实现。另外树上莫队和lca结合了起来，而且一般需要离散化操作。

        回滚莫队：【模板】回滚莫队&不删除莫队 - 洛谷

        一般也需要离散化，右指针好说，是按照从小到大排列的，对于左指针，每次把它拉回块的右边界，再拉到询问的位置，然后再拉回右边界。这样对于左指针在同一块中的查询，在查询的时候可以保存当前右指针的答案，每次只需要更新左指针带来的影响。

        莫队二次离线：【模板】莫队二次离线（第十四分块(前体)） - 洛谷

        适用于一个数对答案的贡献与区间中其他数有关的情况。总体上的思路是求每个数所做的贡献，最后将这些贡献相加或相减。细节很多。先预处理前缀贡献，再模拟莫队，算出第一类贡献，标记第二类贡献，再算出第二类的贡献，最后再相加减。

最后

以上就是单纯星星为你收集整理的11.6第九周总结的全部内容，希望文章能够帮你解决11.6第九周总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。