莫队算法学习记录

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

什么是莫队：

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

什么时候用莫队：

　　　　离线，暴力，1e5

原版莫队：

　　建立区间（x^1/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;
    }

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