概述

莫队算法是由莫涛提出的可以解决一类无修改离线区间查询问题的算法,复杂度为$O(n \sqrt{n})$

若已知$[l_i,r_i]$,我们可以以很少的代价(先视为$O(1)$)转移到$[l_i,r_i+1]$或$[l_i,r_i-1]$($l_i$同理),那么对于区间$[l_1,r_1]$ 到 $[l_2,r_2]$,转移的复杂度为$O(|l_1-l_2| + |r_1 - r_2|)$,这不正是曼哈顿距离么~

所以我们可以将区间视为平面上的点,然后做曼哈顿距离最小生成树
然而这样有些复杂,我们可以用分块的方法来做:
我们将区间分为$\sqrt{n}$个长度为$\sqrt{n}$的块,在每个块内按r排序
我们知道每个块内l最多转移$n$次,r最多转移$n$次,$\sqrt{n}$个块复杂度为$O(2n\sqrt{n})$
块与块间l最多转移$\sqrt{n}$,r最多转移$n$次,$\sqrt{n}$个块复杂度为$O(n + n\sqrt{n})$

所以复杂度为$O(n\sqrt{n})$乘上转移的复杂度

p.s. 若强制在线或者有莫队复杂度不可承受的修改操作,可能要用各种姿势的分块

模板

小Z的袜子(BZOJ2038)

莫队算法一般都是从这题来讲的。
m组询问,问区间内取出两个数相同的概率为多少。

我们设区间内每个数的个数为$x_i$
答案即为$\frac{\sum_i x_i(x_i -1)/2}{C_{r-l+1}^2}$

分母由区间长度决定,分子从$[l_i,r_i]$转移到$[l_i,r_i+1]$,我们假设$a[r_i+1]$在原区间个数为x
更新即为$res -= x(x-1)/2 , res += (x+1)x/2$

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;

const int maxn = 5e4 + 10;

struct Res{
int l,r,id;
LL up,down;
} res[maxn];

int c[maxn],pos[maxn],cur[maxn];
int m,n,B,val;

LL gcd(LL a,LL b)
{
return !b?a:gcd(b,a%b);
}

bool cmp(const Res& a,const Res& b)
{
if(pos[a.l] == pos[b.l]) return a.r < b.r;
else return a.l < b.l;
}

bool cmp_id(const Res& a,const Res& b)
{
return a.id < b.id;
}

void update(int p,int ad)
{
val -= (LL)cur[p]*(cur[p]-1)/2;
cur[p] += ad;
val += (LL)cur[p]*(cur[p]-1)/2;
}

void solve()
{
LL l,r;
val = 0;
l = r = 1;
memset(cur,0,sizeof cur);
update(c[1],1);
for(int i=0;i<m;++i)
{
res[i].down = (LL)(res[i].r - res[i].l + 1)*(res[i].r - res[i].l)/2;
for(;l<res[i].l;++l) update(c[l],-1);
for(;l>res[i].l;--l) update(c[l-1],1);
for(;r<res[i].r;++r) update(c[r+1],1);
for(;r>res[i].r;--r) update(c[r],-1);
res[i].up = val;
//printf("%d %lld\n",res[i].id,val);
}
}

int main()
{
//freopen("test.txt","r",stdin);
int mx = 0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",c+i);
for(int i=0;i<m;++i) scanf("%d %d",&res[i].l,&res[i].r),res[i].id = i,mx = max(mx,res[i].l);
B = sqrt(n);
for(int i=1;i<=mx;++i) pos[i] = i/B;
sort(res,res+m,cmp);
solve();
sort(res,res+m,cmp_id);
for(int i=0;i<m;++i)
{
LL t = gcd(res[i].up,res[i].down);
if(!res[i].up) puts("0/1");
else printf("%lld/%lld\n",res[i].up/t,res[i].down/t);
}
return 0;
}

树上莫队

  • SPOJ COT2
  • 题意: 一棵树,每个节点上有值,每次询问一条链不同的值的个数。

我们对树的dfs序来搞就行了,如下图

树上莫队

每个节点都会出现两次,我们分别取前面的u的后一次(若为v的祖先则取前一次)和v的前一次,注意一个节点若访问两次则抵消,答案需要加上他们的lca

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

const int maxn = 40010;
const int maxm = 1e5 + 10;
const int maxd = 18;
int n,m,B,tot,cur;
int a[maxn],b[maxn],l[maxn],r[maxn],idx[maxn << 1];
vector<int> G[maxn];
int p[maxn][maxd],dep[maxn];
int vis[maxn],cnt[maxn],ans[maxm];

struct Res{
int l,r,rt;
int id;
bool operator<(const Res& rhs) const
{
if(l/B == rhs.l/B) return r < rhs.r;
else return l < rhs.l;
}
} q[maxm];

void dfs(int u,int fa)
{
l[u] = ++tot; idx[tot] = u;
p[u][0] = fa;
dep[u] = dep[fa] + 1;

for(int i=1;i<maxd;++i) p[u][i] = p[p[u][i-1]][i-1];

for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v != fa) dfs(v,u);
}
r[u] = ++tot; idx[tot] = u;
}


int lca(int u,int v)
{
if(dep[u] < dep[v]) swap(u,v);
for(int i=maxd-1;i>=0;--i)
if(dep[p[u][i]] >= dep[v]) u = p[u][i];
if(u == v) return u;
for(int i=maxd-1;i>=0;--i)
if(p[u][i] != p[v][i])
{
u = p[u][i];
v = p[v][i];
}
return p[u][0];
}

int update(int x)
{
if(vis[x])
{
if(--cnt[a[x-1]] == 0) --cur;
}
else if(cnt[a[x-1]]++ == 0) ++cur;

vis[x] ^= 1;
}

void solve()
{
//for(int i=0;i<tot;++i) printf("%d ",idx[i]);
//puts("");
//for(int i=0;i<m;++i) printf("%d %d\n",q[i].l,q[i].r);
//puts("");
int L = q[0].l,R = q[0].l-1;
cur = 0;
for(int i=0;i<m;++i)
{
while(L < q[i].l) update(idx[L++]);
while(L > q[i].l) update(idx[--L]);
while(R < q[i].r) update(idx[++R]);
while(R > q[i].r) update(idx[R--]);
int u = idx[L],v = idx[R];
if(q[i].rt != u && q[i].rt != v) update(q[i].rt);
ans[q[i].id] = cur;
if(q[i].rt != u && q[i].rt != v) update(q[i].rt);
}
for(int i=0;i<m;++i) printf("%d\n",ans[i]);
}


void init()
{
memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
memset(p,0,sizeof p);
for(int i=1;i<maxn;++i) G[i].clear();
tot = 0;
}

int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%d %d",&n,&m) == 2)
{
init();
for(int i=0;i<n;++i) scanf("%d",a+i),b[i] = a[i];
sort(b,b+n);
int pn = unique(b,b+n) - b;
for(int i=0;i<n;++i) a[i] = lower_bound(b,b+pn,a[i]) - b + 1;
for(int i=0;i<n-1;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
B = sqrt(tot) + 1;
for(int i=0;i<m;++i)
{
int u,v;
scanf("%d %d",&u,&v);
q[i].id = i;
if(l[u] > l[v]) swap(u,v);
q[i].rt = lca(u,v);
if(q[i].rt == u) q[i].l = l[u],q[i].r = l[v];
else q[i].l = r[u],q[i].r = l[v];
}
sort(q,q+m);
solve();
}
return 0;
}

题目

  • BZOJ3289
    询问的是区间的逆序对数
    可以用树状数组来做,复杂度$O(n\sqrt{n}logn)$

  • BZOJ2120
    询问区间不同的数的个数,而且有单点修改
    由于修改次数并不多,我们可以在做莫队的过程中加上修改,注意若被修改的元素在查询区间内则需要更新答案。