中国移动怎么样是不是CHINA MOVEITLE

来源：蜘蛛抓取(WebSpider) 时间：2020-01-16 17:54 标签： 中国移动怎么样
0
0
0

会写莫队啦！会写莫队啦！会写莫队啦！
莫队算法的排序以左端点所在块和右端点的大小为关键字
询问区间，\(n\le 30000)\)可以离线，莫队解决关键在于如何添加或删除一个数。我们列出式子之后发现每次操作其实可以等价于两个操作：

  • 把一段区间的数的所有\(f\)向前或向后移
    这里的排序去重令我们想到可以用权徝线段树处理一个数前面有多少个数，所以添加删除可以\(O(logn)\)解决现在考虑如何处理移动问题。
    我们对于权值线段树的每个点记录两个值\((x,y)\)，分别表示当前这个点区间内的答案以及整个区间向后移动一位后的答案。我在这里的做法是用一个标记记录每个区间向右移动的次数（向左为负）然后\(pushdown\)的时候用矩阵快速幂加一下即可。右移矩阵为：


    这里最重要的思想是用离散化+权值线段树处理排序去重区间操作的问題函数记得return返回值。
    还有就是每次要把gs清空也可以用标记实现。

我要回帖

更多关于 中国移动怎么样 的文章

 

随机推荐