[算法模板]莫团队莫团队是一种非常有趣的玄学算法，常用于暴力诈骗。
首先，莫团队通过暴力过渡区间寻求答案。 很明显，完成单组问题的复杂度为((o(left ) x^{*} ) r1-r2||(L1-L2|) ) ) ) right.)。 这里，(x ) )是每次迁移的复杂性。
弹性面团算法的总复杂度为(nsqrtm)。 (我不知道是怎么证明的)
莫团队的精髓是将序列分成块，块的大小也因问题而异。 对于没有修理的普通团队，最佳的阻止方法是
对于带修改的莫团队，阻止方法如下：
带糖团队只需增加一个第三关键词——按时间顺序排序即可。
下面是玄学奇偶校验的另一个优化：
我们只是
intCMP(querya，query b ) {返回belong [ a.l ]==belong [ b.l ]？ a.Rb.r : belong [ a.l ] belong [ b.l ]； )的
intCMP(querya，query b ) return ) Belong[a.L]^Belong[b.L]？ belong [ a.l ] belong [ b.l ] : ((belong [ a.l ]1) )？ a.r b.r : a.r b.r； }就可以了。
具体原理是mo团队——奇偶校验优化细节
这里放着莫队玄学优化牌常见的暴力问题。
[SDOI2009]HH高清项链
# include iostream # include cstdio # include algorithm # include cstring # include cmath # define maxn 500500用户ingnamespacestd； int block[maxn]，val[maxn]，n，m，cnt[1020000]，tot，ans[maxn]； 结构gg { int l，r，id； }q[500500]； inlinevoidadd(intcol ) if (！ cnt[col] ) tot； cnt[col]； }inlinevoiddel(intcol ) if ) CNT[col]==1) tot--； cnt[col]--； }inlineboolCOP(ggx，gg y ) return ) block[x.l]^block[y.l]？ x.ly.l:((block[x.l]1) )？ (x.ry.r ) : ) x.ry.r )； }int main () (Scanf ) ' %d '，n )； for(intI=1； i=n； I ) scanf('%d”，val[i]； }scanf('%d '，m )； intbl=n/sqrt(m*2/3)； for(intI=1； i=n； I ) {block[I]=(I-1 )/bl 1； }for(intI=1； i=m； I ) scanf('%d%d )、q[i].l、q[i].r )； q[i].id=i； }sort(q1，q 1 m，cop )； int l=1，r=1； cnt[val[1]]； tot=1； for(intI=1； i=m； I ) { int tl=q[i].l，tr=q[i].r； while(tll ) {l--； ADD(val[L]； }while(RTR ) ) r； ADD(val[r]； }while(LTL ) ) del ) val[L]； L； }while(TRR ) ) del (val ) r )； r----； } ans[q[i].id]=tot； }for(intI=1； i=m； I ) printf('%d(n )，ans[i]； }
转载于：https://www.cn blogs.com/Gavin Zeng/p/11277204.html