跳转至

莫队

普通莫队

考虑一共有 \(n\) 此询问区间 \([l_i,r_i]\) 上的信息，并且能够在 \(\mathcal O(1)\) 的时间内由 \([l_i,r_i]\) 迭代出: \([l_i+1,r_i]\), \([l_i-1,r_i]\), \([l_i,r_i-1]\), \([l_i,r_i+1]\) 。

那么此时我们按照 \(len = \sqrt{n}\) 分块 ,然后以 \(l\) 所在的块为第一关键字，以 \(r\) 为第二关键字，把询问进行排序。

此时我们按照这个顺序暴力转移，可以证明时间复杂度为 \(\mathcal O(n\sqrt n)\) 。

时间复杂度证明

首先我们考虑左指针：

如果是在块内的移动，每一次最多移动 \(\sqrt n\) 次，所以一共 \(n \sqrt n\) 次。

如果是块之间移动，那么一次最懂移动 \(2\sqrt n\) ，所以一共移动 \(\left(\sqrt n \right)^2 = n\) 。

然后是右指针：

块内因为被排序过，所以总共移动最多: \(n \sqrt n\) 次。

块之间每一次最多 \(n\) 次，所以一共 \(n \sqrt n\) 次。

因此可以得到总时间复杂度为 \(\mathcal O (n\sqrt n)\) 。

一个小优化：

观察下面这个数据1：

1
2
3
4
5
// 设块的大小为 2 (假设)
1 1
2 100
3 1
4 100

此时我们发现处理了第一二个之后来到了: \([2,100]\) 。

此时我们只需要操作两次就可以变成 \([4,100]\) ，但是按照现在的程序会先到 \([3,1]\) 非常的浪费。

所以我们可以考虑一个整块升序，一个降序。

代码：P1494 [国家集训队] 小 Z 的袜子 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
typedef long long ll;
#define PII pair<ll,ll>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=5e4+5;
int n, m;
int c[N];
int len;
PII ans[N];

struct que {
    int id, l, r;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if((l/len)&1) return r<oth.r;
        else return r>oth.r;
    }
}a[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
ll sum=0, cnt[N];
void add(int x) { sum+=cnt[x], cnt[x]++;}
void del(int x) { cnt[x]--, sum-=cnt[x];}
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n>>m;

    for(int i=1; i<=n; i++) cin>>c[i];
    for(int i=1; i<=m; i++) {
        int l, r; cin>>l>>r;
        a[i]=que{i, l, r};
    }

    len=(int)ceil(sqrt(n));
    sort(a+1, a+m+1);

    for(int i=1, l=1, r=0; i<=m; i++) {
        if(a[i].l==a[i].r) {
            ans[a[i].id]=PII{0,1};
            continue;
        }

        while(l>a[i].l) add(c[--l]);
        while(r<a[i].r) add(c[++r]);
        while(r>a[i].r) del(c[r--]);
        while(l<a[i].l) del(c[l++]);

        ans[a[i].id] = PII{
            sum,
            (ll)(a[i].r-a[i].l+1) * (a[i].r-a[i].l) / 2
        };
    }

    for(int i=1; i<=m; i++) {
        ll gcd = __gcd(ans[i].first, ans[i].second);
        if(gcd>1) {
            ans[i].first/=gcd;
            ans[i].second/=gcd;
        }
        printf("%lld/%lld\n", ans[i].first, ans[i].second);
    }

    return 0;
}

带修莫队

对于待修莫队，其实就是增加了一个时间维度。

此时依然相邻状态可以 \(O(1)\) 转移，此时我们令块长为 \(n^{\frac{2}{3}}\) 。

然后通过下面的函数排序：

1
2
3
4
5
bool operator < (const que& oth) const {
    if(l/len != oth.l/len) return l<oth.l;
    if(r/len != oth.r/len) return r<oth.r;
    return t<oth.t; 
}

此时可以证明时间复杂度为 \(\mathcal O(n^{\frac{5}{3}})\) 。

代码：P1903 【模板】带修莫队 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=1e6+5;
int n,m;
int c[N];
int ans[N];

int len;
int cnt1=0, cnt2=0;
struct que {
    int l, r, t, id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if(r/len != oth.r/len) return r<oth.r;
        return t<oth.t; 
    }
}a[N];

struct upde {
    int p,c;
}b[N];

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
int sum=0, cnt[N];
void add(int x) {
    if(cnt[x]==0) sum++;
    cnt[x]++;
}
void del(int x) {
    cnt[x]--;
    if(cnt[x]==0) sum--;
}

/// `x` 代表时间， `y` 代表当前处理i
void cha(int x, int y) {
    if(a[y].l<=b[x].p && b[x].p<=a[y].r) {
        add(b[x].c);
        del(c[b[x].p]);
    }
    swap(c[b[x].p], b[x].c);
}
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>c[i];

    for(int i=1; i<=m; i++) {
        char op; cin>>op;
        if(op=='Q') {
            int l, r; cin>>l>>r;
            a[++cnt1]=que{l,r,cnt2,cnt1};
        } else {
            int p, c; cin>>p>>c;
            b[++cnt2]=upde{p,c};
        }
    }

    len=ceil(pow(n, 2./3));
    sort(a+1, a+cnt1+1);

    for(int i=1, l=1, r=0, t=0; i<=cnt1; i++) {
        while(l>a[i].l) add(c[--l]);
        while(r<a[i].r) add(c[++r]);
        while(l<a[i].l) del(c[l++]);
        while(r>a[i].r) del(c[r--]);
        while(t<a[i].t) cha(++t, i);
        while(t>a[i].t) cha(t--, i);
        ans[a[i].id]=sum;
    }

    for(int i=1; i<=cnt1; i++) {
        cout<<ans[i]<<'\n';
    }

    return 0;
}

树上莫队

括号序列树上莫队

由于普通莫队只能处理序列上的问题，所以我们考虑把树转化为括号序列。

对于一次 DFS ，到达一个点时把 \(x\) 加入，走的时候把 \(x\) 加入。

然后每当我们插入和删除一个节点的时候，我们统计一个 \(vis\) 为他是否已经被计算贡献。

如果已经计算过了，就减去 \(c_x\) ，否则加上。

加上一次询问我们需要查询 \(x \to y\) 路径上的信息，那么分两种情况：

  • \(lca(x,y)=x\) 此时 \(x\) 为 \(y\) 的祖先，那么相当于查询括号序列中 \([in_x,in_y]\) 。

  • \(\texttt{otherwise}\) , 此时相当于查询 \([out_x,in_y] + lca\) 。

参考代码 P4074 [WC2013] 糖果公园 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=1e5+5;
int n, m, q;
int ans[N];
int v[N], w[N], c[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/


int in[N], out[N];
vector<int> arr(1); // 按照DFS顺序的序列
struct LCA {
    vector<int> v[N];

    int cnt;
    int fa[N][20], dep[N];
    void build(int x, int f=0) {
        in[x]=++cnt;
        arr.push_back(x);

        fa[x][0]=f;
        dep[x]=dep[f]+1;
        for(int i=1; i<=19; i++)
            fa[x][i]=fa[fa[x][i-1]][i-1];
        for(auto y: v[x]) {
            if(y==f) continue;
            build(y, x);
        }

        out[x]=++cnt;
        arr.push_back(x);
    }

    int lca(int x, int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=19; i>=0; i--)
            if(dep[fa[x][i]] >= dep[y])
                x=fa[x][i];
        if(x==y) return x;
        for(int i=19; i>=0; i--)
            if(fa[x][i] != fa[y][i])
                x=fa[x][i], y=fa[y][i];
        return fa[x][0];
    }
};
LCA lca;

int len;
int cnt1, cnt2;
struct que {
    int l, r, t, lca ,id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if(r/len != oth.r/len) return r<oth.r;
        return t<oth.t;
    }
}a[N];
pair<int, int> b[N];

int sum, vis[N], cnt[N];
void add(int x) {
    if(!vis[x]) {
        vis[x]=1;
        sum += v[c[x]] * w[++cnt[c[x]]];
    } else {
        vis[x]=0;
        sum -= v[c[x]] * w[cnt[c[x]]--];
    }
}

// 此时的时间 t , 和当前处理的区间 [l,r]
void change(int t, int l, int r) {
    if(vis[b[t].first]) {
        add(b[t].first);
        swap(c[b[t].first], b[t].second);
        add(b[t].first);
    }else swap(c[b[t].first], b[t].second);
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    // stdin
    cin>>n>>m>>q;

    for(int i=1; i<=m; i++) cin>>v[i];
    for(int i=1; i<=n; i++) cin>>w[i];

    for(int i=1; i<n; i++) {
        int x, y; cin>>x>>y;
        lca.v[x].push_back(y);
        lca.v[y].push_back(x);
    }

    for(int i=1; i<=n; i++) cin>>c[i];

    lca.build(1);


    for(int i=1; i<=q; i++) {
        int op, x, y; cin>>op>>x>>y;
        if(op==1) {
            int lc=lca.lca(x, y);
            if(lc==x) a[++cnt1] = que{in[x], in[y], cnt2, 0, cnt1};
            else a[++cnt1] = que{ out[x], in[y], cnt2, lc, cnt1};
        } else {
            b[++cnt2] = make_pair(x, y);
        }
    }

    // solve

    len=ceil(pow(2*n, 2./3));
    sort(a+1, a+cnt1+1);

    for(int i=1, l=1, r=0, t=0; i<=cnt1; i++) {

        while(l>a[i].l) add(arr[--l]);
        while(r<a[i].r) add(arr[++r]);
        while(l<a[i].l) add(arr[l++]);
        while(r>a[i].r) add(arr[r--]);

        while(t<a[i].t) change(++t, l, r);
        while(t>a[i].t) change(t--, l, r);

        if(a[i].lca) add(a[i].lca);
        ans[a[i].id]=sum;
        if(a[i].lca) add(a[i].lca);
    }

    for(int i=1; i<=cnt1; i++) cout<<ans[i]<<'\n';

    return 0;
}

代码细节

通过真是代码可以发现，对于第二种情况可能出现 \(out_x > in_y\) 的情况。

但是其实此时莫队是支持的，因为你不要把莫队当作一个区间，而是一个二维平面上的点: \((x,y)\) ，然后通过 \((x,y)\) 可以得到 \((x,y-1), (x,y+1), (x+1,y), (x-1,y)\) 。

按照这种理解莫队问题其实就变成了找一个路径经过所有的点，要求他们的哈夫曼路径最短。通过分块，就是莫队了。

我们发现这种办法还是有相当的局限性的, 因为他其实只是转换成序列，然后只能且介树上路径的信息。

真 · 树上莫队

%% 等待补充 %%

回滚莫队

有的时候，题目我们发现是通过莫队实现 2，但是我们发现对于增加区间可以通过 \(\mathcal O(1)\) 完成，但是对于删除就不行（比如说是某一个权值的最大值）。

为了解决这个问题，我们可以选择通过更多的添加操作去代替, 比如说我们把询问的区间进行分组，然后每一组取他们的重合区间，于是都转化为扩张了。

具体来说，先正常，进行分类讨论：

  • 当 \(l,r\) 在同一个块中，直接暴力进行计算。

  • 当 \(l\) 所在的块 \([L,R]\) 相比上一个询问发生改变，此时令 \(l = R+1, r = R\) 。

  • 当 \(l,r\) 不在一个块中：

    • 扩展右端点达到查询区间（由于保证在这一区间内，右端点单调）。

    • 扩展左端点 （由于每一次会重新回到 \(R+1\) ，而当前查询的每一个 \(l < R+1\)）。

    • 回溯左端点（这里一般是会把扩展左端点时的答案记录为 \(\texttt{Tmp}\) ，然后回溯时只需要删除其在桶中进行的操作）

示例代码 P5906 【模板】回滚莫队&不删除莫队 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
const int N=4e5+5;
int n, m;
int c[N];

int len;
struct que {
    int l, r, id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        return r<oth.r;
    }
}a[N];
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
#define R(x) min(((((x)/len)+1)*len-1), n)

int ans[N];

namespace LSH {
    int tot, a[N];
    void main() {
        sort(a+1, a+tot+1);
        tot=unique(a+1, a+tot+1)-a-1;
        for(int i=1; i<=n; i++) {
            c[i]=lower_bound(a+1, a+tot+1, c[i])-a;
        }
    }
}

int pos[N];
int st[N], ed[N];
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>c[i];
        LSH::a[++LSH::tot]=c[i];
    }

    LSH::main();

    cin>>m;
    for(int i=1; i<=m; i++) {
        int l, r; cin>>l>>r;
        a[i]=que{l, r, i};
    }

    len=ceil(sqrt(n));
    sort(a+1, a+m+1);

    int Last_Block=-1, Ans=0;

    for(int i=1, l=0, r=0; i<=m; i++) {
        if(a[i].l/len == a[i].r/len) {
            for(int j=a[i].l; j<=a[i].r; j++) {
                if(!pos[c[j]]) pos[c[j]]=j;
                ans[a[i].id]=max(ans[a[i].id], j-pos[c[j]]);
            }
            for(int j=a[i].l; j<=a[i].r; j++)
                pos[c[j]]=0;
            continue;
        }

        if(a[i].l/len != Last_Block) {
            for(int j=l; j<=r; j++)
                st[c[j]]=ed[c[j]]=0;
            r=R(a[i].l), l=r+1;
            Ans=0;
        }

        while(r<a[i].r) {
            ++r, ed[c[r]]=r;
            if(!st[c[r]]) st[c[r]]=r;

            Ans=max(Ans, r-st[c[r]]);
        }

        int Tmp=Ans, L=l;
        while(l>a[i].l) {
            l--;
            if(!ed[c[l]]) ed[c[l]]=l;
            Tmp=max(Tmp, ed[c[l]]-l);
        }

        ans[a[i].id]=Tmp;

        while(l<L) {
            if(ed[c[l]]==l) ed[c[l]]=0;
            l++;
        }

        Last_Block=a[i].l/len;
    }

    for(int i=1; i<=m; i++) cout<<ans[i]<<'\n';

    return 0;
}

注意

有些一些简单的最大最小值问题实际上是可以使用普通莫队做的：

比如说要维护一个区间中出现最多次的数字出现的个数（参见 P1997 faebdc 的烦恼）。

这个时候我们可以使用以下办法解决：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int sum, cnt[N], t[N];
void add(int x) { 
    t[cnt[x]]--;
    t[++cnt[x]]++;
    sum=max(sum, cnt[x]);
}
void del(int x) { 
    t[cnt[x]]--;
    if(sum==cnt[x] && !t[cnt[x]])
        sum--;
    t[--cnt[x]]++;
}

  1. 来自 OI-WIKI。 ↩

  2. 可能是看题目标签 ↩