莫队——优雅的暴力

暴力出奇迹,$n^2$ 过百万

普通莫队

[SDOI2009]HH的项链

虽然这道题 $n$ 有 $10^6$ 但卡一卡还能过

首先考虑最暴力的暴力,直接枚举就行了

然后莫队是怎样去优化这个暴力的?

先定义两个指针 $l,r$ 表示当前已经求出区间 $[l,r]$ 的答案,对于询问 $[L,R]$,

实际上只需要移动 $l,r$ 即可,如果有一种办法能够使移动的次数最小,时间复杂度会不会降下来呢?

莫队正是利用了这一点,考虑离线处理所有询问,对区间左端点分块,对于左端点在同一块中的两个询问,

按照右端点编号排序,否则,按照左端点编号排序,这里有一个优化,奇偶性排序,就是奇数块升序排,偶数块降序排,

对于一些大数据可能会有用.那么这么排为什么会快?

先考虑左端点,左端点只会有两种移动方式,在块内移动与再两个块间移动

块内移动的距离显然是不超过块的大小的,这里定义块的大小为 $\sqrt{n}$,一共 $m$ 此询问,那么时间复杂度就是 $O(m\sqrt{n})$

在两个块之间移动,考虑最远距离 $2\sqrt{n}$,总时间复杂度也是 $O(m\sqrt{n})$ 的

再考虑右端点,因为对于左端点再同一个块的询问,右端点是单调递增的,那么就是 $O(n)$,

一共有 $\sqrt{n}$ 个块,总时间复杂度就是 $n\sqrt{n}$

综上所述,时间复杂度可以认为是 $O(n\sqrt{n})$ 的,有时候如果TLE了可以尝试修改块的大小

(这里没有画图,可以自己结合图像方便理解)

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define get(x) ((x) / len)
using namespace std;
const int N = 1e6 + 5;

int n, len, cnt[N], w[N], ans[N];
struct query
{
    int id, l, r;
    bool operator < (const query t) const
    {
        int a = get(l), b = get(t.l);
        if (a != b)
            return a < b;
        else
        {
            if (a & 1)
                return r < t.r;
            else
                return r > t.r;
        }
    }
} q[N];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') 
    {   
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int n;
    n = read();
    for (int i = 1; i <= n; i++)
        w[i] = read();
    int m;
    m = read();
    len = 1720;
    for (int i = 1; i <= m; i++)
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    sort(q + 1, q + 1 + m);
    int res = 0;
    for (int k = 1, i = 0, j = 1; k <= m; k++)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) 
        {
            int t = w[++i];
            if (!cnt[t]) res++;
            cnt[t]++;
        }
        while (i > r) 
        {
            int t = w[i--];
            cnt[t]--;
            if (!cnt[t]) res--;
        }
        while (j > l) 
        {
            int t = w[--j];
            if (!cnt[t]) res++;
            cnt[t]++;
        }
        while (j < l) 
        {
            int t = w[j++];
            cnt[t]--;
            if (!cnt[t]) res--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

带修莫队

[国家集训队]数颜色 / 维护队列

多了个修改操作而已,只需要再多开一个指针 $t$ 表示当前已经处理到第 $t$ 个修改

那么排序规则就是使 $t$ 单调递增, 对左端点与右端点分块,其他的与普通莫队类似

只不过在 $t$ 转移时,有个比较取巧的方式,就是每次修改时交换序列里的值与修改操作的值,

这样,在回退的时候也可以直接交换,会方便一些.

那么带修莫队的时间复杂度又是多少呢?还是 $O(n\sqrt{n})$?.

我们设块长为 $a$, 那么一共就有 $\frac{n}{a}$ 块

考虑左端点,同样时在块内与块间移动,时间复杂度 $O(am+2a\frac{n}{a})$

考虑 $t$,类似普通莫队,时间复杂度 $O(m\frac{n^2}{a^2})$

最后考虑右端点,块内移动与 $l$ 类似,考虑块间,对于左端点的每一个块, $r$ 都会移动 $n$ 步,所以实际按复杂度就是 $O(am+\frac{n^2}{a})$

但是 $max(O(am+n),O(m\frac{n^2}{a^2}),O(am+\frac{n^2}{a}))$ 该怎么取呢?

首先,我们肯定要让 $a\ge\sqrt{n}$,不然 $O(m\frac{n^2}{a^2})$ 就是 $n^2$ 级别的了

所以忽略掉较小项就是 $max(O(am),O(m\frac{n^2}{a^2}))$

要让这个最小就是 $am=m\sqrt{\frac{n^2}{a^2}}\Rightarrow a=n^{\frac{2}{3}}$

时间复杂度就是 $O(n^{\frac{5}{3}})$,卡一卡能过

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define p first
#define val second
#define get(x) ((x) / len)
using namespace std;
const int N = 2e5 + 5;
typedef pair<int, int> PII;

PII my[N];
int w[N], cnt, tot, len, tim[N * 10], ans[N];
struct query
{
    int id, l, r, t;
    bool operator < (const query a) const
    {
        int al = get(l), ar = get(r);
        int bl = get(a.l), br = get(a.r);
        if (al != bl) return al < bl;
        if (ar != br) return ar < br;
        return t < a.t;
    }
} q[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
    {
        char opt;
        int l, r;
        scanf(" %c", &opt);
        if (opt == 'Q')
        {
            scanf("%d%d", &l, &r);
            cnt++;
            q[cnt] = query({cnt, l, r, tot});
        }
        else
        {
            scanf("%d%d", &l, &r);
            my[++tot] = make_pair(l, r);
        }
    }       
    len = pow(n, 2.0 / 3);
    sort(q + 1, q + 1 + cnt);
    for (int k = 1, i = 0, j = 1, t = 0, res = 0; k <= cnt; k++)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, to = q[k].t;
        while (i < r)
        {
            int tp = w[++i];
            if (!tim[tp]) res++;
            tim[tp]++;
        }
        while (i > r)
        {
            int tp = w[i--];
            tim[tp]--;
            if (!tim[tp]) res--;
        }
        while (j > l)
        {
            int tp = w[--j];
            if (!tim[tp]) res++;
            tim[tp]++;
        }
        while (j < l)
        {
            int tp = w[j++];
            tim[tp]--;
            if (!tim[tp]) res--;
        }
        while (t < to)
        {
            t++;
            if (my[t].p >= j && my[t].p <= i)
            {
                int pi = my[t].p;
                tim[w[pi]]--;
                if (!tim[w[pi]]) res--;
                if(!tim[my[t].val]) res++;
                tim[my[t].val]++;
            }
            swap(my[t].val, w[my[t].p]);
        }
        while (t > to)
        {
            if (my[t].p >= j && my[t].p <= i)
            {
                int pi = my[t].p;
                tim[w[pi]]--;
                if (!tim[w[pi]]) res--;
                if(!tim[my[t].val]) res++;
                tim[my[t].val]++;
            }
            swap(my[t].val, w[my[t].p]);
            t--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= cnt; i++)
        printf("%d\n", ans[i]);
    return 0;
}

回滚莫队

【模板】回滚莫队&不删除莫队

对于一些不好维护删除操作,而比较好维护添加操作的要求,比如求max,可以用回滚莫队

排序还是一样的排,但实现方式略有不同,对于左端点在同一块内的询问,我门将它分为块内与块间两个部分

对于块内的部分,直接暴力就行了,反正不会超过$\sqrt{n}$,对于块间的部分,因为是单调的,所以也不会超过 $n\sqrt{n}$

那为什么要叫回滚呢?就是每次在处理询问时,我们记录一个备份,对于块内的询问,我们在记录完答案后还原,因为块外是单调的,所以不需要管

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define pl first
#define pr second
#define INF 0x3f3f3f3f
#define get(x) ((x) / len)
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<int, int> PII;

PII bp[N], pi[N];
int len, w[N], ans[N], temp[N], val[N], cnt;
struct query
{
    int id, l, r;
    bool operator < (const query a) const
    {
        int x = get(l), y = get(a.l);
        if (x != y) return x < y;
        else return r < a.r;
    }
} q[N];

inline int find(int x)
{
    int l = 1, r = cnt;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (temp[mid] < x)
            l = mid + 1;
        else if (temp[mid] == x)
            return mid;
        else
            r = mid - 1;
    }
}

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    // freopen("1.in", "r", stdin);
    int n = read();
    for (int i = 1; i <= n; i++)
        val[i] = w[i] = read();
    sort(w + 1, w + 1 + n);
    for (int i = 1; i <= n; i++)
        if (temp[cnt] != w[i])
            temp[++cnt] = w[i];
    for (int i = 1; i <= n; i++)
        w[i] = find(val[i]);
    int m = read();
    for (int i = 1; i <= m; i++)
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    len = sqrt(n);
    sort(q + 1, q + 1 + m);
    for (int x = 1; x <= m;)
    {
        int y = x;
        while (y <= m && get(q[x].l) == get(q[y].l)) y++;
        int R = get(q[x].l) * len + len;
        while (x < y && q[x].r <= R)
        {
            int res = 0;
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for (int k = l; k <= r; k++)
                bp[w[k]] = pi[w[k]];
            for (int k = l; k <= r; k++)
            {
                bp[w[k]].pr = k;
                if (!bp[w[k]].pl)
                    bp[w[k]].pl = k;
                res = max(res, k - bp[w[k]].pl);
            }
            ans[id] = res;
            x++;
        }
        int res = 0, i = R, j = R + 1;
        while (x < y)
        {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            while (i < r)
            {
                i++, pi[w[i]].pr = i;
                if (!pi[w[i]].pl)
                    pi[w[i]].pl = i;
                res = max(res, i - pi[w[i]].pl);
            }            
            int backup = res;
            while (j > l)
            {
                if (!pi[w[--j]].pr)
                    pi[w[j]].pr = j;
                res = max(res, pi[w[j]].pr - j);
            }
            while (j <= R)
            {
                if (pi[w[j]].pr == j)
                    pi[w[j]].pr = 0;
                j++;
            }
            ans[id] = res;
            res = backup;
            x++;
        }
        for (int i = 1; i <= cnt; i++)
            pi[i].pl = pi[i].pr = 0;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

树上莫队

对于树上问题,一个比较普遍的做法就是转化为序列问题,那么对于树上莫队,我们可以将他转化为欧拉序

记录每个点在欧拉序中第一个出现的位置 $fir$ 与第二个出现的位置 $sec$,对于当前的 $u,v$ 之间的路径 若 $u$ 为 $v$ 的父亲,就是直接在欧拉序 $[fir_u,fir_v]$ 中只出现了一次的数

若 $u$, $v$ 在两颗子树内,就找 $[sec_u,fir_v]$ 中只出现了一次的数,然后再加上 $lca(u,v)$ 的值.

这里想一想就能明白,统计次数和普通莫队类似可以参考代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define get(x) ((x) / len)
using namespace std;
const int N = 1e5 + 5;

bool st[N];
int fir[N], sec[N], seq[N], top;
int head[N], ver[N], net[N], idx;
int w[N], temp[N], val[N], cnt[N], len;
int depth[N], fa[N][21], ans[N], tot;
struct query
{
    int id, l, r, p;
    bool operator < (const query a) const
    {
        int x = get(l), y = get(a.l);
        if (x != y) return x < y;
        if (x & 1) return r < a.r;
        return r > a.r;
    }
} q[N];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (x == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline void add(int a, int b)
{
    net[++idx] = head[a], ver[idx] = b, head[a] = idx;
    net[++idx] = head[b], ver[idx] = a, head[b] = idx;
}

void dfs(int u, int f)
{
    seq[++top] = u, fir[u] = top;
    depth[u] = depth[f] + 1, fa[u][0] = f;
    for (int i = 1; i <= 17; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (v == f) continue;
        dfs(v, u);
    }
    seq[++top] = u, sec[u] = top;
}

inline int lca(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 17; i >= 0; i--)
        if (depth[fa[u][i]] >= depth[v])
            u = fa[u][i];
    if (u == v) return u;
    for (int i = 17; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

inline void modify(int x, int& res)
{
    st[x] ^= 1;
    if (st[x] == 0)
    {
        cnt[w[x]]--;
        if (!cnt[w[x]]) res--;
    }
    else 
    {
        if (!cnt[w[x]]) res++;
        cnt[w[x]]++;
    }
}

inline int find(int x)
{
    int l = 1, r = tot;
    while (l <= r)
    {
        int mid = (l + 1) >> 1;
        if (temp[mid] < x)
            l = mid + 1;
        else if (temp[mid] == x)
            return mid;
        else
            r = mid - 1;
    }
}

int main()
{
    int n, m;
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        val[i] = w[i] = read();
    sort(w + 1, w + 1 + n);
    for (int i = 1; i <= n; i++)
        if (temp[tot] != w[i])
            temp[++tot] = w[i];
    for (int i = 1; i <= n; i++)
        w[i] = find(val[i]);
    for (int i = 1; i < n; i++)
        add(read(), read());
    dfs(1, 0);
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        if (fir[u] > fir[v]) swap(u, v);
        int p = lca(u, v);
        if (u == p) q[i] = query({i, fir[u], fir[v], 0});
        else q[i] = query({i, sec[u], fir[v], p});
    }
    sort(q + 1, q + 1 + m);
    for (int k = 1, L = 1, R = 0, res = 0; k <= m; k++)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, p = q[k].p;
        while (R < r) modify(seq[++R], res);
        while (R > r) modify(seq[R--], res);
        while (L > l) modify(seq[--L], res);
        while (L < l) modify(seq[L++], res);
        if (p) add(seq[p], res);
        ans[id] = res;
        if (p) add(seq[p], res);
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

二次离线莫队

传送门

树上回滚带修二次离线莫队

这个东西似乎没有,不过有树上带修莫队,就是树上莫队与带修莫队结合一下就行了

先放这,以后来填