博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html
$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$
引入
$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$
普通莫队
$\;$
核心
$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$
时间复杂度
$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)
$\;$
左端点
$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$
右端点
$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$
Code
#include <bits/stdc++.h>
const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块
return a.r < b.r; // 右端点所属位置
}
int main() {
scanf("%d", &n);
sq = (int)sqrt(n);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
std::sort(b + 1, b + n + 1);
nn = std::unique(b + 1, b + n + 1) - b - 1;
for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
//----------------- 上面是离散化部分,不多赘述
scanf("%d", &m);
for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
std::sort(ask + 1, ask + m + 1, cmp);
int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针
for(int i=1;i<=m;i++) {
int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点
while(x < l) { // 左端点向右移,区间缩小
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}
while(x > l) { // 左端点向左移,区间变大
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}
while(y < r) { // 右端点向右移,区间变大
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}
while(y > r) { // 右端点向左移,区间缩小
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}
ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}
带修莫队
$\;$
一般的莫队实质上是不支持修改操作的,但如果这个修改操作很简单,比较容易维护,我们还是可以实现的。
而带修莫队的分块方式与普通莫队不同。
现在我们把序列分为$n^{\frac{1}{3}}$个块,每个块的长度为$n^{\frac{2}{3}}$
对于操作来说,我们把修改和询问分开。
对于询问:左端点所在块为第一关键字,右端点所在块为第二关键字,时间(输入的时候排第几行)为第三关键字进行排序。
那么,与普通莫队类似。只需多维护一个修改的操作。
即:假设两个询问的时间分别为$t_1,t_2$,我们只需把$[t_1,t_2]$这段时间内的修改操作执行一遍(时光正流或倒流)
$\;$
时间复杂度
$\;$
时间指针
当左右端点所在块不变时。对于每种两个块组合的方案,因为时间是递增的,所以最多执行$O(n)$次,一共有$n^{\frac{2}{3}}$种方案,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,也只会出现$n^{\frac{2}{3}}$次,每次$O(n)$,故为$O(n^{\frac{5}{3}})$
当左端点所在块变化时,只会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
右端点
当左右端点所在块不变时。$n$次询问,每次最多移动$n^{\frac{2}{3}}$,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
当左端点所在块变化时,与上面类似,也为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
左端点
当左端点所在块不变时,与上面的情况一样。为$O(n^{\frac{5}{3}})$
而最多会变$n^{\frac{1}{3}}$次,因为是按左端点所在块为第一关键字排序的。所以变化这一部分是$O(n)$的
综上:为$O(n^{\frac{5}{3}})$
$\;$
Code
$\;$
例题:P1903 数颜色
https://www.luogu.com.cn/problem/P1903
#include <bits/stdc++.h>
#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
int l, r, t, pos;
}ask[N];
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
return a.t < b.t;
}
bool g(int d) {
return (x <= d && d <= y);
}
void gg(int x, int y) {
cnt[x] --; cnt[y] ++;
if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
scanf("%d%d", &n, &m);
sq = pow(n, 3.0 / 4);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
for(int i=1;i<=m;i++) {
char op[5]; int l, r;
scanf("%s", op);
scanf("%d%d", &l, &r);
if(op[0] == 'Q') {
++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
}
else {
cur[i].fi = l; cur[i].se = r;
fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
}
}
std::sort(ask + 1, ask + k + 1, cmp);
int ti = 0;
for(int i=1;i<=k;i++) {
int t = ask[i].t, l = ask[i].l, r = ask[i].r;
while(ti < t) {
if(!cur[ti + 1].fi) {
ti ++; continue;
}
if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
a[cur[ti + 1].fi] = cur[ti + 1].se;
ti ++;
}
while(ti > t) {
if(!fur[ti].fi) {
ti --; continue;
}
if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
a[fur[ti].fi] = fur[ti].se;
ti --;
}
while(x < l) {
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}
while(x > l) {
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}
while(y < r) {
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}
while(y > r) {
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}
ans[ask[i].pos] = res;
}
for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
return 0;
}
$\;$
树上莫队
$\;$
核心
$\;$
只不过把序列的问题搬到了树上,区间也就变成了一条链。
我们将树分块。
具体实现方法是:维护一个栈,代表目前待选的点的集合S。dfs到某个点u的时候,遍历它的所有子树并统计目前集合S的大小,在遍历的过程中,如果发现集合S的大小已超过规定的块大小,将这些点分为一块。
可以注意到,因为我们是按dfs的顺序进行编号的。所以相邻编号的块在树上也一定是相邻的,这样就会满足莫队的复杂度。
而因为不是在序列上,所以我们不能简单的对左右指针+1或-1
假如上一次询问的链是$(x,y)$,这次是$(u,v)$,那么只需对$(x,u)$和$(y,v)$这两条链上的点的标记进行取反操作。
最终$(u,v)$上的所有点会被标为1。这个可以通过画图理解。
不过在实现的时候,还要注意一些细节:比如说LCA可能要特殊处理,可以参考代码理解。
那么剩余的就和普通、带修莫队一样了。
$\;$
Code
$\;$
例题:P4074 糖果公园
https://www.luogu.com.cn/problem/P4074
$\;$
#include <bits/stdc++.h>
const int N = 100010;
int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int read() {
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return f * x;
}
int dfs(int u, int fa) {
int re = 0;
dfn[u] = ++idx;
f[u][0] = lst[u] = fa;
dep[u] = dep[fa] + 1;
for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int i=0;i<G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
re += dfs(v, u);
if(re >= S) {
scc ++;
while(re)
id[stk[top --]] = scc, re --;
}
}
stk[++top] = u;
return re + 1;
}
struct node {
int l, r, pos, t;
}ask[N];
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) {
if(id[a.l] & 1) return id[a.r] < id[b.r];
return id[a.r] > id[b.r];
}
return a.pos < b.pos;
}
int lca(int x, int y) {
if(x == y) return x;
if(dep[x] < dep[y]) std::swap(x, y);
int ch = dep[x] - dep[y], er = 0;
while(ch) {
if(ch & 1) x = f[x][er];
ch >>= 1; er ++;
}
if(x == y) return x;
for(int i=19;~i;i--) {
if(f[x][i] == f[y][i]) continue;
x = f[x][i]; y = f[y][i];
}
return f[x][0];
}
void change(int d, int v) {
if(vis[d]) {
ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
ans = ans + 1ll * w[++ tim[v]] * val[v];
c[d] = v;
}
else c[d] = v;
}
void modify(int x) {
if(vis[x]) {
vis[x] = 0;
ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --];
}
else {
vis[x] = 1;
ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
}
}
void make_tag(int u, int v) {
while(u != v) {
if(dep[u] > dep[v]) modify(u), u = f[u][0];
else modify(v), v = f[v][0];
//printf("%d %d\n", u, v);
}
}
int main() {
n = read(); m = read(); q = read();
S = pow(n, 0.666);
for(int i=1;i<=m;i++) val[i] = read();
for(int i=1;i<=n;i++) w[i] = read();
for(int i=1;i<n;i++) {
int u, v;
u = read(); v = read();
G[u].push_back(v); G[v].push_back(u);
}
dfs(1, 0);
scc ++;
for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
for(int i=1;i<=q;i++) {
int op, l, r;
op = read(); l = read(); r = read();
if(!op) {
upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
}
else {
if(dfn[l] > dfn[r]) std::swap(l, r);
ask[++k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
}
}
std::sort(ask + 1, ask + k + 1, cmp);
for(int i=1;i<ask[1].t;i++) {
if(!upd[i]) continue;
change(d[i], upd[i]);
}
x = ask[1].l; y = ask[1].r;
make_tag(x, y); modify(lca(x, y));
res[ask[1].pos] = ans;
modify(lca(x, y));
for(int i=2;i<=k;i++) {
int l = ask[i].l, r = ask[i].r;
// time
int t = ask[i].t, p = ask[i - 1].t;
while(p < t) {
p ++;
if(upd[p]) change(d[p], upd[p]);
}
while(p > t) {
if(upd[p]) change(d[p], pre[p]);
p --;
}
make_tag(x, l);
make_tag(y, r);
modify(lca(l, r));
res[ask[i].pos] = ans;
modify(lca(l, r));
x = l; y = r;
}
for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
return 0;
}