区间信息的维护与查询

发布于 2019-03-23  113 次阅读


做题

------------分鸽线

莫队算法

莫队主要是用于离线处理一类只有查询不带修改的区间信息问题。
什么?这不Segment_tree?
Segment_tree处理此类问题时是通过拉分别拉一棵左右子树来进行合并,所以掐指一算o(ls+rs)
注意是子树。所以线段树在此类问题中会挂掉。
那怎么办?
考虑暴力,枚举每一个区间然后存储信息,复杂度是o(nm)其中m是询问次数。
显然易炸。
这时我们考虑优化一下,如果我们已求出[L,R]的信息,那我们是不是可以在o(1)的时间内知道[L+1,R][L-1,R][L,R+1][L,R-1]的信息?然后我们慢慢扩张到所求区间。复杂度是平面上的曼哈顿距离的最小生成树。
可跟暴力好像没什么区别呀?
我们把序列分块,询问左端点所在的分块的序号为第一关键字,右端点的大小为第二关键字进行排序,按照排序好的顺序计算,复杂度就会大大降低。
- 块相同时,r单调递增,所以r是O(n)的。共有n^{0.5}块,所以这一部分时间复杂度是O(n^{1.5})
- 块转移时,r最多变化n,由于有n^{0.5}块,所以这一部分时间复杂度是n^{1.5}
- 块相同时,左端点变化最多变化n^{0.5},而转移时,不会超过2 \sqrt{n}。由于有m次询问(和n同阶),所以时间复杂度是n^{1.5}
于是就是总复杂度就是O(n^{1.5})了。

一些乱七八糟的优化

  • 分块优化:听说分成\frac{n} { \sqrt {m\times\frac{2}{3} }}更快哦
    原来

    	int block = int (sqrt(n));
    	rep(1,m) pos[i] = (i-1)/block+1;
    

    优化

    	int block = n/sqrt(m*(2/3));
    	//每个块的编号是a[i].l / block;
    
  • 奇偶排序优化
    在原来的排序中,分块相同时,右指针是按从小到大排的。这样在转移时会走多余的路程。
    所以我们为了让右指针一直单调递增or递减,这样就会快的多。
    莫队本身是个暴力,就是靠分块才能维持的了生活。而如果是正常排序的话,右指针路程会重复。而只要让相邻两个快保持单调就会快很多
    原来

    	return pos[a.l] ^ pos[b.l]?a.l < b.l:a.r < b.r;
    

    优化

    	return (a.l / block) ^ (b.l /block) ?a.l < b.l:((a[i].l / block) &1) ?a.r <b.r:a.r>b.r)
    

    「」

train

「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)
「Luogu1972」「SDOI2009HH的项链」
「Luogu2709」「小B的询问」


我是一个局部环,你是我的唯一极大理想。