基础莫队

· · 算法·理论

今天讲一下基础的莫队算法。

算法思路

暴力

每次统计每个数有几次，再累加，时间复杂度为 \Omicron(nm)。
0分（全 TLE） 不是这题卡这么紧。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[50010]; 
int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    while(m--)
    {
        int l,r,ans = 0;
        scanf("%d%d",&l,&r);
        map<int,int> c;//直接开数组也可以
        for(int i = l;i <= r;i++)
            c[a[i]]++;//累加
        for(int i = 1;i <= k;i++)
            ans += c[i] * c[i];//加上平方
        cout << ans << endl;
    }
    return 0;
}

优化

思路

上面的暴力代码是在线的，而换成离线呢？
在线定义：输入后会立刻输出结果。
离线定义：输入完才会按顺序输出结果。

那我们就可以优化，下一个答案根据上一个答案转移出来。
定义一个 add 和 del 函数，用来添加和删除数据。

代码

那每次会对答案加上多少呢？

$(c_i + 1) ^ 2 - c_i ^ 2 \\ = (c_i + 1 + c_i)(c_i + 1 - c_i)\\ =2c_i + 1

减去也一样。

=(c_i + c_i - 1)(c_i - c_i + 1)\\ =2c_i - 1

上代码

#include<bits/stdc++.h>
using namespace std;
int n, m, k, a[50010], c[50010];
long long ans;
struct point
{
    int l, r;
}q[50010];
void add(int x)
{
    ans += 2 * c[x] + 1;
    c[x]++;
}
void del(int x)
{
    ans -= 2 * c[x] - 1;
    c[x]--;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        scanf ("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        scanf ("%d%d", &q[i].l, &q[i].r);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        int ql = q[i].l, qr = q[i].r;
        /*注意，应该先写扩大再缩小，不然可能会负数*/
        /*先扩大再添加*/
        while (l > ql) l--, add(a[l]);
        while (r < qr) r++, add(a[r]);
        /*先删除再缩小*/
        while (l < ql) del(a[l]), l++;
        while (r > qr) del(a[r]), r--;
        cout << ans << endl;
    }
    return 0;
}

全 TLE

时间复杂度

add 和 del 的时间复杂度为 \Omicron(1)，
每次扩大或缩小时间复杂度最坏为 \Omicron(n)，
一共执行了 m 次扩大缩小。
时间复杂度为 \Omicron(nm) 没优化？。

再优化

思路和代码

我们发现如果排序了数组就可以优化时间复杂度，可如何排序呢？

我们把一个 a 这个数组分成几个区间，每个区间长度为 B。

$\Box\Box|\Box\Box|\Box\Box|\Box\Box|\Box$。 我们统一排序右端点，得到以下表达式： `cmp`:$\begin{cases}x.l < y.l & \text{if} & \frac{x.l}{B} = \frac{y.l}{B}\\ x.r < y.r & \end{cases}

写出代码：

bool cmp(point x, point y)
{
    if (x.l / B != y.l / B) return x.l < y.l;
    return x.r < y.r;
}

那 B 选几合适呢？
设 \sqrt{n}，这样就可以分成 n 个区间。

上代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, k, a[50010], c[50010], B;
long long now, ans[50010];//now为当前的答案，ans[i]为第i个询问的答案
struct point
{
    int l, r, id;
}q[50010];
bool cmp(point x, point y)
{
    if (x.l / B != y.l / B) return x.l < y.l;
    return x.r < y.r;
}
void add(int x)
{
    now += 2 * c[x] + 1;
    c[x]++;
}
void del(int x)
{
    now -= 2 * c[x] - 1;
    c[x]--;
}
int main()
{
    cin >> n >> m >> k, B = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf ("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        scanf ("%d%d", &q[i].l, &q[i].r), q[i].id = i;//记录每个点原来的id
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        int ql = q[i].l, qr = q[i].r id = q[i].id;
        while (l > ql) l--, add(a[l]);
        while (r < qr) r++, add(a[r]);
        while (l < ql) del(a[l]), l++;
        while (r > qr) del(a[r]), r--;
        ans[id] = now;
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << endl; 
    return 0;
}

AC记录。

时间复杂度分析

设第 i 个区间的最大 l 为 max_i。
排序后：max_1 \le max_2 … \le max_{\sqrt{n}}。
每一次操作最坏的时间复杂度为 \Omicron(n)。 所有块的总和就是\Omicron(n\sqrt{n})。
重点分析 l：因为每一次改变的时间复杂度都是 \Omicron(max_i-max_{i-1}) 的，所以在同一块中时间复杂度为 \Omicron(\sqrt{n}(max_i-max_{i-1}))。
求和

& O(\sqrt{n}(\max{}_1-1)+\sqrt{n}(\max{}_2-\max{}_1)+\sqrt{n}(\max{}_3-\max{}_2)+\cdots+\sqrt{n}(\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1))} \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_1-1+\max{}_2-\max{}_1+\max{}_3-\max{}_2+\cdots+\max{}_{\lceil\sqrt{n}\rceil-1}-\max{}_{\lceil\sqrt{n}\rceil-2}+\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1)}) \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_{\lceil\sqrt{n}\rceil-1}))\\ \end{aligned}

最后，欢迎来到我的博客玩。