Java教程

莫队算法学习记录

本文主要是介绍莫队算法学习记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是莫队:

    莫队是一种用于处理询问区间值的暴力离线算法,思路是通过移动两个指针到对应的区间来计算结果,精华是合理分块并依次处理。

什么时候用莫队:

    离线,暴力,1e5

原版莫队:

  建立区间(x1/2):

  

ll size=sqrt(n),bnum=ceil((double)n/size);
    for(ll i = 1; i <= bnum; ++i) for(ll j = (i - 1) * size + 1; j <= i * size; ++j) belong[j] = i;

 

  排序:

bool cmp(Query a,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));
}

  

  区间移动:

for(ll i=1;i<=q;i++)
    {
        ll ql=query[i].l,qr=query[i].r;
        while(l<ql) now -=(--num[a[l++]]) ;
        while(l>ql) now += num[a[--l]]++;
        while(r<qr) now += num[a[++r]]++;
        while(r>qr) now -= (--num[a[r--]]);
        ans1[query[i].id]=now;
    }

 

这篇关于莫队算法学习记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!