莫队算法入门

标签：type   http   amp   顺序   int   有一个   cst   数据   时间复杂度   

Talk about 莫队

莫队算法，是莫涛dalao发明的一个神奇的优化暴力算法，它使用看似很simple的指针移动操作以及分块的思想来将复杂度优化至\(O(n\sqrt n)\)

莫队的基本思想也很简单：

1. 离线操作，在后面会提到我们通过排序来降低复杂度
2. 设之前我们以及求出了区间\([l,r]\)的答案，那么我们考虑如何快速转移到\([l+1,r],[l-1,r],[l,r-1],[l,r+1]\)
3. 每一次利用之前的信息跳动指针即可得出答案

不过如果是这样的话，只要出题人把数据造坑一点，让你\(l,r\)指针一直左右移动，就可以卡到\(O(n^2)\)我还不如写暴力

所以莫队的精髓来了，既然都是询问，那我们是否可以通过适当地改变询问的顺序来让\(l,r\)跳转的幅度更小一点。

所有我们可以利用分块的思想来优化：对于两个询问，若在其\(l\)在同块，那么将其\(r\)作为排序关键字，若\(l\)不在同块，就将\(l\)作为关键字排序（这就是双关键字）

这样就可以优化时间复杂度么，我们看一下严格的证明（摘自大米饼的博客）：

首先，枚举\(m\)个答案，就一个\(m\)了。设分块大小为\(unit\)，元素\(i\)所属的快为\(blk_i\)

分类讨论：

①\(l\)的移动：若下一个询问与当前询问的\(l\)所在的块不同，那么只需要经过最多\(2\cdot unit\)步可以使得\(l\)成功到达目标.复杂度为：\(O(m\cdot unit)\)

②\(r\)的移动：\(r\)只有在\(blk_l\)相同时才会有序（其余时候还是疯狂地乱跳，你知道，一提到乱跳，那么每一次最坏就要跳\(n\)次！），\(blk_l\)什么时候相同？在同一块里面\(blk_i\)相同。对于每一个块，排序执行了第二关键字: \(r\)。所以这里面的\(r\)是单调递增的，所以枚举完一个块，\(r\)最多移动n次。总共有\(\frac{n}{unit}\)个块:复杂度为：\(O(\frac{n^2}{unit})\)

总结：\(O(n\cdot unit+\frac{n^2}{unit})\)（\(n,m\)同级，就统一使用\(n\)）

根据基本不等式得：当\(n=\sqrt n\)时，得到莫队算法的真正复杂度：\(O(n\sqrt n)\)

然后除此以外莫队还有一个更加NB的常数优化，即在cmp时写成：

return blk[a.l]b.r));

其实也很好理解吧，当左端点同块时判断一下当前快编号的奇偶性，尽量让右端点波动范围较小（类似波浪形）

经典板子题——区间不同元素个数

板子题参考：SPOJ D-query

大致题意：给定一个数组，每次询问一个区间内有多少不同的元素

很简单的莫队板子题，对于每一次加入新的数时都判断一下这个数之前是否出现过即可，删除时同理。

别忘记离散化，CODE

#include
#include
#include
#include
using namespace std;
const int N=30005,M=200005;
struct data
{
    int l,r,ans,id;
}q[M];
int a[N],b[N],n,m,size,tot,blk[N],res,L,R,cnt[N];
inline char tc(void)
{
    static char fl[100000],*A=fl,*B=fl;
    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
    x=0; char ch; while (!isdigit(ch=tc()));
    while (x=(x9) write(x/10);
    putchar(x%10+‘0‘);
}
inline bool cmp1(data a,data b)
{
    return blk[a.l]b.r));
}
inline bool cmp2(data a,data b)
{
    return a.id>1; if (b[mid]==x) return mid;
        if (b[mid]q[i].l) add(a[--L]); while (Lq[i].r) del(a[R--]);
        q[i].ans=res;
    }
    for (sort(q+1,q+m+1,cmp2),i=1;i

莫队算法入门

标签：type   http   amp   顺序   int   有一个   cst   数据   时间复杂度   

原文地址：https://www.cnblogs.com/cjjsb/p/9539388.html