莫队初探

众所周知，分块是一种￥#@%￥#的暴力。

而暴力+分块等于啥呢

￥#@%￥#的暴力莫队！

莫队是什么？克罗地亚男子足球队队长莫德里奇国家队队长莫涛发表的算法尊称为莫队

具体的来说，只要一个答案区间 $[L,R]$的答案可以在 $O(1)$ 的时间复杂度下扩展到 $[L+1,R],[L-1,R],[L,R+1],[L,R-1]$并且出题人不强制在线，就可以愉快的使用莫队算法计算答案了！

莫队算法的核心是通过上一次的询问 $[L_1,R_1]$ 来更新当前询问 $[L_2,R_2]$。时间复杂度是$ left | L_2-L_1 ight |+left |R_2-R_1 ight | $。

但很显然，这样的算法是很naive的=_=。如果前一次的$L$与当前的$L$差距过大，你会愉快的TLE。我们需要对其进行优化。

众所周知，分块是一种￥#@%￥#的暴力。

而暴力+分块等于啥呢

更￥#@%￥#的暴力莫队！

我们将所有的询问按照左端点$L$所在的块的序号$pos[L]$为第一关键字排序，以右端点$R$所在的块的序号$pos[R]$为第二关键字排序，这样便避免了上面提到的问题。这样做的理论复杂度是$O(n sqrt n)$的，但实际复杂度是$O(玄学？？？？？？？能过就好）$。

核心代码具体实现大概是下面这个样子↓↓↓

int update(int...,int ...)
{
    ....;
    return .....;
}
void solve()
{
    int l=1,r=0;
    for(int i=1;i<=q;i++)
    {
        int size=(x[i].r-x[i].l+1);
        int fm=size*(size-1);
        for(;r<x[i].r;r++) 
            update(a[r+1],...);//注意扩展区间时要忽略开头(在L,R中计算过了)
        for(;r>x[i].r;r--) 
            update(a[r],...);//缩小区间时要忽略结尾(结尾并没有计算)
        for(;l<x[i].l;l++) 
            update(a[l]...);//同上 
        for(;l>x[i].l;l--) 
            update(a[l+1]...);
        ...//特判 
    }
}

莫队初步差不多就这样了。还有一种带修改莫队，具体的就是在操作后加一维x表示操作序号，在修改时可以向$[L,R,x pm 1]$扩展了。在扩展中若发现过程中操作序号发生改变，就把中间的操作干掉。

口胡，不要介意。

$Luogu P1903$是带修莫队裸题，$Luogu P 1972$是普通莫队裸题。

0725 fix 带修莫队

具体地说，第三维的移动可以理解为时光倒流（或加速），所以要将跳过的操作所做的贡献加回去；

代码↓↓↓

void work(int x,int y)
{
    if(b[x].pos<=a[y].r&&b[x].pos>=a[y].l)
    {
        delet(c[b[x].pos]);
        add(b[x].num);
    }
    swap(b[x].num,c[b[x].pos]);//小优化 在更改完这次的颜色后 下次要撤回这次操作时不需要再写一个函数 比如这次将7修改成2 下次撤回操作的时候可以直接把2改回7 
}
for(;l<a[i].l;l++)
    delet(c[l]);
for(;l>a[i].l;l--)
    add(c[l-1]);
for(;r<a[i].r;r++)
    add(c[r+1]);
for(;r>a[i].r;r--)
    delet(c[r]);
for(;now<a[i].id;now++)
    work(now+1,i);
for(;now>a[i].id;now--)
    work(now,i);

$LHC$是我们的红太阳，没有他我们会死！！！！！