莫队

基础莫队

适用范围：已知 $[l,r]$ 的答案，可以 $O(1)$ 的得出 $[l-1,r], [l,r-1], [l+1,r], [l,r+1]$ 的答案，时间复杂度 $O(n \sqrt n)$

例题：P1972 [SDOI2009] HH的项链

方法：

离线处理，将数组分块，将询问左端点按块的编号排序，右端点按编号排序，每次处理询问类似双指针暴力从上一个询问区间转移到下一个询问区间，单次复杂度 $O(\sqrt n)$ ，总复杂度 $O(m\sqrt n)$

优化：排序时偶数块右端点从小到大排序，奇数块右端点从大到小排序

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
#include<bits/stdc++.h>
using namespace std;

const int N=50005,M=2e5+5,S=1e6+5;

int n,m,len;
int w[N],ans[M];

int get(int x){
    return x/len;
}

struct Query{
    int id,l,r;
    friend bool operator<(const Query a,const Query b){
        int i=get(a.l),j=get(b.l);
        if(i!=j)return i<j;
        if(i&1)return a.r>b.r;
        return a.r<b.r;
    }
}q[M];
int cnt[S];


void add(int x,int &res){
    if(!cnt[x])res++;
    cnt[x]++;
}

void del(int x,int &res){
    cnt[x]--;
    if(!cnt[x])res--;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }
    cin >> m;
    len=max(1.0,sqrt((double)n*n/m));
    for(int i=1;i<=m;i++){
        int l,r;
        cin >> l >> r;
        q[i]={i,l,r};
    }
    sort(q+1,q+m+1);
    for(int k=1,i=1,j=0,res=0;k<=m;k++){
        int id=q[k].id,l=q[k].l,r=q[k].r;
        while(i<l)del(w[i++],res);
        while(i>l)add(w[--i],res);
        while(j<r)add(w[++j],res);
        while(j>r)del(w[j--],res);
        ans[id]=res;
    }
    for(int i=1;i<=m;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

带修改的莫队

有修改的基础莫队

例题：P1903 [国家集训队] 数颜色 / 维护队列

分析：

新增一维 t 表示这次询问查询的是第 t 次修改之后的值，这样每次 t+1/t-1 都可以 $O(1)$ 完成（具体实现见代码）。

排序时先按左端点所在块编号，然后按右端点所在块编号，然后按 t 排序 。

理论块长 $^3\sqrt{nt}$ ，实际 $^3\sqrt {n^2}$ 也可以。

修改t时有一点小优化，具体细节见代码。

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
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5,S=1e6+5;

int n,m,len;
int w[N],ans[N];

int get(int x){
    return x/len;
}

struct Query{
    int id,l,r,t;
    friend bool operator<(const Query a,const Query b){
        int al=get(a.l),ar=get(a.r);
        int bl=get(b.l),br=get(b.r);
        if(al!=bl)return al<bl;
        if(ar!=br)return ar<br;
        return a.t<b.t;
    }
}q[N];

struct Modify{
    int p,c;
}c[N];

int cnt[S],mq,mc;

void add(int x,int &res){
    if(!cnt[x])res++;
    cnt[x]++;
}

void del(int x,int &res){
    cnt[x]--;
    if(!cnt[x])res--;
}

int main(){
    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[2];
        scanf("%s",opt);
        if(opt[0]=='Q'){
            int l,r;
            scanf("%d%d",&l,&r);
            q[++mq]={mq,l,r,mc};
        }
        else{
            int x,k;
            scanf("%d%d",&x,&k);
            c[++mc]={x,k};
        }
    }
    len=max(1.0,pow(1.0*n*n,1.0/3));
    sort(q+1,q+mq+1);
    for(int k=1,t=0,i=1,j=0,res=0;k<=mq;k++){
        int id=q[k].id,tm=q[k].t,l=q[k].l,r=q[k].r;
        
        while(i<l)del(w[i++],res);
        while(i>l)add(w[--i],res);
        while(j<r)add(w[++j],res);
        while(j>r)del(w[j--],res);
        while(t>tm){
            if(c[t].p>=i&&c[t].p<=j){
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
            t--;
        }
        while(t<tm){
            t++;
            if(c[t].p>=i&&c[t].p<=j){
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
            
        }
        ans[id]=res;
    }
    for(int i=1;i<=mq;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

回滚莫队

当基础莫队删除/插入（以下以删除为例，插入同理）操作难以 $O(1)$ 实现（如取 max）时，使用回滚莫队。

AT_joisc2014_c 歴史の研究

分析：

由于删除难以实现，因此只操作增加

把操作先按左端点块编号排序，然后按右端点排序，接下来从左到右计算每个块的答案。

当左右端点都在这个块中时，由于块长为 $\sqrt n$ ，因此暴力即可。

当左端点在块中，右端点在右侧的其他块时，由于右端点一定是单调的，因此从当前询问转移到下一个询问时右端点一定只有增加操作，因此每次处理询问后删除所有增加的左端点（即先增加右端点，然后记录当前答案，增加完左端点后恢复答案和 cnt 数组）

注意清空

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+5;

int n,m,len;
int w[N],cnt[N];
ll ans[N];

int get(int x){
    return x/len;
}

struct Query{
    int id,l,r;
    friend bool operator<(const Query a,const Query b){
        int i=get(a.l),j=get(b.l);
        if(i!=j)return i<j;
        return a.r<b.r;
    }
}q[N];

vector<int>nums;

void add(int x,ll &res){
    cnt[x]++;
    res=max(res,1ll*cnt[x]*nums[x]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    len=max(1.0,sqrt(n));
    for(int i=1;i<=n;i++){
        cin >> w[i];
        nums.push_back(w[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++){
        w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin >> l >> r;
        q[i]={i,l,r};
    }
    sort(q+1,q+m+1);
    
    for(int x=1;x<=m;){
        int y=x;
        while(y<=m&&get(q[y].l)==get(q[x].l))y++;
        int right=get(q[x].l)*len+len-1;
        
        //求块内的询问——暴力
        while(x<y&&q[x].r<=right){
            ll res=0;
            int id=q[x].id,l=q[x].l,r=q[x].r;
            for(int k=l;k<=r;k++)add(w[k],res);
            ans[id]=res;
            for(int k=l;k<=r;k++)cnt[w[k]]--;
            x++;
        }
        
        //求块外的询问——莫队
        ll res=0;
        int i=right+1,j=right;
        while(x<y){
            int id=q[x].id,l=q[x].l,r=q[x].r;
            while(j<r)add(w[++j],res);
            ll backup=res;
            while(i>l)add(w[--i],res);
            ans[id]=res;
            while(i<right+1)cnt[w[i++]]--;
            res=backup;//回滚
            x++;
        }
        memset(cnt,0,sizeof cnt);
        
    }
    for(int i=1;i<=m;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

树上莫队

首先考虑如何把树上问题转化成序列问题。

首先求出树的欧拉序（即 根+子树+根），然后不难发现以下规律：

记 $first[u]$ 为 $u$ 在欧拉序中第一次出现的位置，$last[u]$ 为 $u$ 在欧拉序中最后一次出现的位置，则对于两个点 $x,y$ 满足 $first[x]<first[y]$ ，则

  • 若 $lca(x,y)=x$，则 $x$ 到 $y$ 的路径为欧拉序中 $[first[x],first[y]]$ 中只出现一次的点
  • 若 $lca(x,y) \not = x$，则 $x$ 到 $y$ 的路径为欧拉序中 $[last[x],first[y]]$ 中只出现一次的点和 $lca(x,y)$

这样就把树上问题转化为了序列问题。

例题：AcWing 2534 树上计数2/SP10707 COT2 - Count on a tree II

处理序列时使用一个数组 $st$ ，每次增加/删除一个点 $x$ 时将 $st[x] \oplus 1$ ，若 $st[x]=0$，则表示出现了 0 或 2 次，删去，否则表示出现了 1 次，加入。

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m;
int len;
int w[N],ans[N],cnt[N];
int euler[N],idx,first[N],last[N];
bool st[N];

int get(int x){
    return x/len;
}

struct Query{
    int id,l,r;
    friend bool operator<(const Query x,const Query y){
        int i=get(x.l),j=get(y.l);
        if(i!=j)return i<j;
        if(i&1)return x.r>y.r;
        return x.r<y.r;
    }
}q[N];

vector<int>to[N];
int fa[N][30],d[N];

void dfs(int u,int f){
    d[u]=d[f]+1;
    fa[u][0]=f;
    euler[++idx]=u;
    first[u]=idx;
    for(auto x:to[u]){
        if(x!=f)dfs(x,u);
    }
    euler[++idx]=u;
    last[u]=idx;
}

void init(){
    for(int k=1;k<30;k++){
        for(int i=1;i<=n;i++){
            fa[i][k]=fa[fa[i][k-1]][k-1];
        }
    }
}

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

vector<int>nums;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> w[i];
        nums.push_back(w[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++){
        w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin >> x >> y;
        to[x].push_back(y);
        to[y].push_back(x);
    }
    dfs(1,0);
    init();
    for(int i=1;i<=m;i++){
        int l,r;
        cin >> l >> r;
        q[i]={i,first[l],first[r]};
    }
    sort(q+1,q+m+1);
    for(int k=1,i=1,j=0;k<=m;k++){
        int id=q[k].id,l=q[k].l,r=q[k].r,res;
        while(i<l)change(i++,res);
        while(i>l)change(--i,res);
        while(j<r)change(++j,res);
        while(j>r)change(j--,res);
        if(lca(euler[l],euler[r])!=euler[l]){
            change(lca(euler[l],euler[r]),res);
            ans[id]=res;
            change(lca(euler[l],euler[r]),res);
        }
        else{
            ans[id]=res;
        }
        
    }
    for(int i=1;i<=m;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

二次离线莫队

例题：P4887 【模板】莫队二次离线（第十四分块(前体)）

题目大意：给定一个序列，每次询问一个区间内异或和二进制下有 $k$ 个 1 的二元组个数。

分析：

分析操作，主要难点是处理区间的扩展，下面以 $[L,R]$ 扩展到 $[L,R+1]$ 为例分析如何操作。

当增加一个数 $w[R+1]$ 时，就需要求 $[L,R]$ 中有多少个数与这个数配对（即异或和有 $k$ 个1），也就是这个数对 $res$ 的贡献。

记 $S_i$ 表示前 $i$ 个数中与 $w[R+1]$ 配对的数的个数，则这个数的贡献就是 $S_R-S_{L-1}$。

首先考虑如何求 $S_R$ ，记 $f_i$ 表示 $w_1 \sim w_i$ 中有多少个数与 $w_i+1$ 配对，则 $S_R=f_R$。可以递推求 $f_i$，维护一个辅助数组 $g_x$ ，表示前 $i$ 个数中有多少个与 $x$ 配对，则 $f_i=x_{w_{i+1}}$ 。

接下来考虑如何求 $S_{L-1}$，可以发现很难直接算出来，因此可以先进行一遍莫队，记录所有要求的 $S_{L-1}$ ，然后离线求出。

其余操作略有不同，但推导过程相同，详见代码。

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

typedef long long ll;

int n,m,k,len;
int w[N];
ll ans[N];

int get(int x){
    return x/len;
}

struct Query{
    int id,l,r;
    ll res;
    friend bool operator<(const Query &a,const Query &b){
        int i=get(a.l),j=get(b.l);
        if(i!=j)return i<j;
        return a.r<b.r;
    }
}q[N];

struct Range{
    int id,l,r,t;
};
vector<Range>range[N];
int f[N],g[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }
    vector<int>nums;
    for(int i=0;i<1<<14;i++){
        if(__builtin_popcount(i)==k){
            nums.push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        for(auto y:nums){
            g[w[i]^y]++;
        }
        f[i]=g[w[i+1]];
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin >> l >> r;
        q[i]={i,l,r};
    }
    len=sqrt(n);
    sort(q+1,q+n+1);
    for(int i=1,L=1,R=0;i<=m;i++){
        int l=q[i].l,r=q[i].r;
        //S(R)-S(L-1)
        if(R<r)range[L-1].push_back({i,R+1,r,-1});
        while(R<r)q[i].res+=f[R++];
        //-(S(R-1)-S(L-1))=-S(R-1)+S(L-1)
        if(R>r)range[L-1].push_back({i,r+1,R,1});
        while(R>r)q[i].res-=f[--R];
        //-(S(R)-S(L))=-S(R)+S(L)=-S(R)+f(L-1)+!k
        if(L<l)range[R].push_back({i,L,l-1,-1});
        while(L<l)q[i].res+=f[L-1]+!k,L++;
        //S(R)-S(L-1)=S(R)-(f(L-2)+!k)
        if(L>l)range[R].push_back({i,l,L-1,1});
        while(L>l)q[i].res-=f[L-2]+!k,L--;
    }
    
    memset(g,0,sizeof g);
    for(int i=1;i<=n;i++){
        for(auto y:nums)++g[w[i]^y];
        for(auto&rg:range[i]){
            int id=rg.id,l=rg.l,r=rg.r,t=rg.t;
            for(int x=l;x<=r;x++){
                q[id].res+=g[w[x]]*t;
            }
        }
    }
    for(int i=2;i<=m;i++){
        q[i].res+=q[i-1].res;
    }
    for(int i=1;i<=m;i++){
        ans[q[i].id]=q[i].res;
    }
    for(int i=1;i<=m;i++){
        cout << ans[i] << '\n';
    }
    
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~