莫队算法

莫队算法可以一个可高效解决绝大多数离线+无修改+区间查询问题的算法。这类问题具体是指：如果知道[L,R]的答案时，可以在O(g(n))的时间下得到[L,R−1],[L,R+1],[L−1,R],[L+1,R]的答案的话，就可以O ( n n ⋅ g ( n ) ) O(n\sqrt n · \mathrm{g}(n))O(n

n

⋅g(n))的时间内求出所有查询。

假设我们算完[L,R]的答案后现在要算[L′,R′]的答案。由于可以在O(1)的时间下得到[L,R−1],[L,R+1],[L−1,R],[L+1,R]的答案，所以计算[L′,R′]的答案耗时|L−L′|+|R−R′|。如果把询问[L,R]看做平面上的点a(L,R)，询问[L′,R′]看做点b(L′,R′)的话，那么时间开销就为两点的曼哈顿距离。

具体实现

我们先对序列分块，每块长度为sqrt(n)，然后以询问左端点所在的块为第一关键字，右端点的大小为第二关键字进行排序

然后每个区间由它的上一个区间推出来,虽然单次询问仍可能是O(n),

但是在块中每次询问l的移动最大为sqrt(n)，r的移动总和最大为n，块与块之间的移动最大为n

所以总复杂度为O((n+m)sqrt(n))

我这里给出莫队的模板，

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 50010
#define LL long long
using namespace std;
int n, m, k, unit;
struct Mo
{
    int l;
    int r;
    int id;
    int pos;
    bool operator<(const Mo &rhs) const
    {
        if (pos == rhs.pos)
            return r < rhs.r;
        else
            return l < rhs.l;
    }
} a[N];
int b[N], cnt[N];
LL Ans[N];
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    unit = sqrt(n + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
        a[i].id = i;
        a[i].pos = a[i].l / unit;
    }
    sort(a + 1, a + 1 + m);
    int l = 1, r = 0;
    LL ans = 0;
    for (int i = 1; i <= m; i++)
    {
        while (l > a[i].l)
        {
            l--;
            //操作
            ans += 
        }
        while (r < a[i].r)
        {
            r++;
            //操作
            ans +=  
        }
        while (l < a[i].l)
        {
            ans -=  
            //操作
            l++;
        }
        while (r > a[i].r)
        {
            ans -=  
            //操作
            r--;
        }
        Ans[a[i].id] = ans;
    }
    for (int i = 1; i <= m; i++)
        printf("%lld\n", Ans[i]);
    return 0;
}