2018-06-21

高级数据结构-莫队

问题类型

适用于询问是一段区间[L,R]，可以离线，并且时间复杂度一个根号跑的过的情况下。

解决方案

我们把n个数分成sqrt(n)个块，每个块就会有sqrt(n)个数。
假设i被分到了Belong[i]这个块。
我们先把所有询问按Belong[L]从小到大排序（如果Belong[L]相等，就按R从小到大）。
然后我们就把前一个区间暴力扩展删除到现在的区间为止。
L指针每一个询问最多移动sqrt(n)次，总共 q sqrt(n)。
R指针每不同的Belong[L]最多移动n次，最多sqrt(n)个块，总共 n sqrt(n)。
所以总时间复杂度为(n + q) * sqrt(n)。

代码演示

int cmp(node X, node Y)
{
    return Belong[X.l] == Belong[Y.l] ? X.r < Y.r : Belong[X.l] < Belong[Y.l];
}

void Insert()

void Delete()

int main()
{
    Init();
    sort(Q + 1, Q + m + 1, cmp);
    int L = 1, R = 0;
    rep(i, 1, m)
    {
        while (L < Q[i].l) Delete(L++);
        while (L > Q[i].l) Insert(--L);
        while (R > Q[i].r) Delete(R--);
        while (R < Q[i].r) Insert(++R);
        Ans[Q[i].id] = Calc();
    }
}