当前位置：首页 > news >正文

各种莫队算法

news 2025/7/6 1:42:02

莫队算法，是一种以分块为基础的维护区间[1,n]的离线算法，主打一个优雅的暴力

应用场景：对于q个询问，每次询问区间[l,r]

算法核心：我们将区间[1,n]按每块长度为 $\sqrt{n}$ 进行分块，则block[i]表示下标为i的元素所在的块的编号。我们对q个询问以block[l]作为第一关键字，r作为第二关键字由小到大排序，然后再逐一处理询问。假设我们现在遍历到的区间为[curl,curr]，那么对于排序后的第i个询问的区间[l,r]，我们暴力地将curl逐一移动到l并更新我们所要维护的区间信息，暴力地将curr逐一移动到r并更新我们所要维护的区间信息。

这时可能就要问了，那这和我直接按l为第一关键字，r为第二关键字来排序询问有什么不同呢？

区别就在于：当我们的询问的左端点l在第i个块的时，curr最多移动n次，而我们又只有 $\sqrt{n}$ 个块，因此curr移动的时间复杂度为 $O(n\sqrt{n})$ ，而对于左端点，我们遍历q次询问，每次询问curl最多移动 $\sqrt{n}$ 次，因此curl移动的时间复杂度为 $O(q\sqrt{n})$ ，若q和n为同一个数量级，则我们处理询问的总时间复杂度为 $O(n\sqrt{n})$ 。而暴力按l,r为关键字的排列方式处理询问的时间复杂度显然为 $O(n^2)$ 。可见，我们只是稍微修改了一下排序比较方式，就大大减少了其时间复杂度。

普通莫队：

按上述思路实现的算法即为普通莫队，我们还可以对其进行一定的优化：当块编号为奇数的时候，右端点按由小到大排序；当块编号为偶数的时候，右端点按由大到小排序。这样以来，我们刚遍历完奇数块，右端点不断往远处跑，然后到下一个偶数块的时候，右端点就可以在回来的时候就把询问的右端点处理完毕了，也是一种优化方式。

题目链接：P3709 大爷的字符串题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

该题目的意思是要求出区间[l,r]的众数个数，那我们可以用莫队暴力维护区间各个数字的出现次数，出现频率最多的就为众数，但是我们缩减区间的时候更新众数就麻烦一点，这里，我们再记录一个出现频率的计数，当删除时且该频率的计数也清除到0时，我们更新众数个数为比该数小1的数即可

实现代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2E5 + 10;
int n, m, len;
int a[N], inp[N], block[N], idx[N];
int cnt[N], ans[N], MAX;
int cnt2[N];
struct query {int l, r, id;bool operator<(const query tmp)const {return (block[l] ^ block[tmp.l]) ? block[l] < block[tmp.l] : (block[l] & 1) ? r<tmp.r : r>tmp.r;}
}Q[N];inline void read(int& des) {int x = 0; char c = getchar();while (c < '0' || c>'9') c = getchar();while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + c - '0';c = getchar();}des = x;
}void write(int x) {if (x > 9) write(x / 10);putchar(x % 10+'0');
}void add(int cur) {cnt2[cnt[idx[cur]]++]--;cnt2[cnt[idx[cur]]]++;MAX = max(MAX, cnt[idx[cur]]);
}void del(int cur) {cnt2[cnt[idx[cur]]--]--;cnt2[cnt[idx[cur]]]++;if (cnt[idx[cur]]+1 == MAX && cnt2[MAX] == 0) {MAX = cnt[idx[cur]];}}
int main() {read(n); read(m);len = sqrt(n);for (int i = 1; i <= n; i++) block[i] = i / len + (i % len > 0);for (int i = 1; i <= n; i++) { read(a[i]); inp[i] = a[i]; }sort(inp + 1, inp + n + 1);int tot = unique(inp + 1, inp + n + 1) - inp - 1;for (int i = 1; i <= n; i++) idx[i] = lower_bound(inp + 1, inp + tot + 1, a[i]) - inp;for (int i = 1; i <= m; i++) {read(Q[i].l); read(Q[i].r);Q[i].id = i;}sort(Q + 1, Q + m + 1);int curl = 1, curr = 0;for (int i = 1, l, r; i <= m; i++) {l = Q[i].l; r = Q[i].r;while (curl > l) add(--curl);while (curl < l) del(curl++);while (curr < r) add(++curr);while (curr > r) del(curr--);ans[Q[i].id] = MAX;}for (int i = 1; i <= m; i++) {putchar('-'); write(ans[i]); putchar('\n');}return 0;
}

带修莫队：

上述提到莫队是一种离线算法，因为其需要对询问进行排序。但如果题目不要求强制在线，我们也可以用莫队维护动态的修改。

具体思路：我们记录下每个操作以及询问的时间戳，然后对询问再加入以时间戳t为第三关键字排序。当我们处理询问的时候，若当前时间戳小于询问的时间戳，则我们先进行若干项操作，直到时间戳相同，同时更新区间信息。

题目链接：P1903 [国家集训队] 数颜色 / 维护队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

实现代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 150000, M = 1E6 + 10;
int n, m, len;
int block[N];
int col[N];
struct query {int l, r, time, id;bool operator<(const query tmp)const {return (block[l] ^ block[tmp.l]) ? block[l] < block[tmp.l] : (block[r] ^ block[tmp.r]) ? block[r] < block[tmp.r] : time < tmp.time;}
}Q[N];
struct chan {int pos, col;
}C[N];
int cntq, cntc;
int ans[N], cnt[M], res;
inline void read(int& des) {int x = 0; char c = getchar();while (c < '0' || c>'9')c = getchar();while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + c - '0';c = getchar();}des = x;
}
void write(int x) {if (x > 9)write(x / 10);putchar(x % 10 + '0');
}
int main() {read(n); read(m);len = pow(n,2.0/3.0);for (int i = 1; i <= n; i++) block[i] = i / len + (i % len > 0);for (int i = 1; i <= n; i++) read(col[i]);char flag[10]; cntc = 1;for (int i = 1; i <= m; i++) {scanf("%s", flag);if (flag[0] == 'Q') {read(Q[++cntq].l); read(Q[cntq].r); Q[cntq].time = cntc; Q[cntq].id = cntq;}else if(flag[0] == 'R') {read(C[++cntc].pos); read(C[cntc].col);}}sort(Q + 1, Q + 1 + cntq);int l, r, t;int curl = 1, curr = 0, tnow = 1;for (int i = 1; i <= cntq; i++) {l = Q[i].l; r = Q[i].r; t = Q[i].time;while (curl < l) res -= !--cnt[col[curl++]];while (curl > l) res += !cnt[col[--curl]]++;while (curr < r) res += !cnt[col[++curr]]++;while (curr > r) res -= !--cnt[col[curr--]];while (tnow < t) {tnow++;if (C[tnow].pos >= l && C[tnow].pos <= r) {res -= !(--cnt[col[C[tnow].pos]]);res += !cnt[C[tnow].col]++;}swap(C[tnow].col, col[C[tnow].pos]);}while (tnow > t) {if (C[tnow].pos >= l && C[tnow].pos <= r) {res -= !(--cnt[col[C[tnow].pos]]);res += !cnt[C[tnow].col]++;}swap(C[tnow].col, col[C[tnow].pos]);tnow--;}ans[Q[i].id] = res;}for (int i = 1; i <= cntq; i++) {write(ans[i]); putchar('\n');}
}

树上莫队：

莫队是处理区间询问的，那么如果我们想要处理树上路径的询问，该如何处理呢？

我们可以将树上路径转换为一段区间，具体做法为：

假设树上有n个结点，我们对树进行dfs,对每个端点，记录first[u]以及last[u]，first[u]是第一次访问节点时的序号，last[u]是访问完u的所有子树后，回到u自身的序号，这样，我们就形成了一段长度为2*的欧拉序。在欧拉序中，区间[frist[u],last[u]]显然包含了u的子树的所有结点v的first[v]以及last[v]。则在路径u到v所对应的欧拉序区间中，出现次数为奇数的点一定在路径(u,v)中，而出现次数为偶数的点一定不在路径(u,v)中。倘若我们需要得到路径(u,v)的信息，我们先使first[u]＞first[v]，我们分两种情况来讨论：

1.u是 $lca_{u,v}$ ，则我们只需统计区间[frist[u],first[v]]中出现次数为奇数的的点的信息即可

2.u不是 $lca_{u,v}$ ，则我们需要统计[last[u],first[v]]中出现次数为奇数的点的信息，并加上 $lca_{u,v}$ 的信息即可

这里查找lca的方法采用倍增

题目链接：SPOJ.com - Problem COT2

实现代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int N = 4E4 + 10, M = 1E5 + 10;
int col[N], idx[N],inp[N];
int h[N], nxt[N<<1], tto[N<<1], tot;
int first[N], last[N], dfn[N << 1], num;
bool vis[N];
int lg[N], fa[21][N], dep[N];
int block[N << 1], cnt[N];
int ans[M];
struct query {int u, v, id;int l, r;int lca;bool operator<(const query tmp)const {return (block[l] ^ block[tmp.l]) ? block[l] < block[tmp.l] : (block[l] & 1) ? r<tmp.r : r>tmp.r;}
}Q[M];
int n, m, len,res;
inline void read(int& des) {int x = 0; char c = getchar();while (c < '0' || c>'9') c = getchar();while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + c - '0';c = getchar();}des = x;
}
void write(int x) {if (x > 9) write(x / 10);putchar(x % 10 + '0');
}
void add(int a, int b) {tto[++tot] = b;nxt[tot] = h[a];h[a] = tot;
}
void dfs(int u) {for (int i = h[u], v; v = tto[i]; i = nxt[i]) {if (vis[v]) continue; vis[v] = true;fa[0][v] = u; dep[v] = dep[u] + 1;for (int j = 1; j < lg[dep[v]]; j++) fa[j][v] = fa[j - 1][fa[j - 1][v]];first[v] = ++num;dfn[num] = v;dfs(v);}last[u] = ++num;dfn[num] = u;
}
int getlca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);while (dep[u] > dep[v]) u = fa[lg[dep[u] - dep[v]]- 1][u];if (u == v) return v;for (int i = lg[dep[u]]-1; ~i; i--) {if (fa[i][u] ^ fa[i][v]) {u = fa[i][u]; v = fa[i][v];}}return fa[0][u];
}
void chan(int cur) {vis[dfn[cur]] ^= 1;if (vis[dfn[cur]]) {if (!cnt[idx[dfn[cur]]]) res++;cnt[idx[dfn[cur]]]++;}else {cnt[idx[dfn[cur]]]--;if (!cnt[idx[dfn[cur]]]) res--;}}
int main() {read(n); read(m);for (int i = 1; i <= n; i++) { read(col[i]); inp[i] = col[i]; }sort(inp + 1, inp + n + 1);int tot = unique(inp + 1, inp + n + 1) - inp - 1;for (int i = 1; i <= n; i++) idx[i] = lower_bound(inp + 1, inp + tot + 1,col[i]) - inp;for (int i = 1,u,v; i <n; i++) {read(u); read(v);add(u, v); add(v, u);}for (int i = 1; i <=n; i++) lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);//log2 + 1vis[1] = true; first[1] = ++num;dfn[num] = 1; dep[1] = 1;dfs(1);for (int i = 1; i <= m; i++) {read(Q[i].u); read(Q[i].v);if (first[Q[i].u]>first[Q[i].v]) swap(Q[i].u, Q[i].v);Q[i].lca = getlca(Q[i].u, Q[i].v);if (Q[i].lca == Q[i].u) { Q[i].l = first[Q[i].u]; Q[i].r = first[Q[i].v];}else {Q[i].l = last[Q[i].u]; Q[i].r = first[Q[i].v];}Q[i].id = i;}len = sqrt(n << 1);for (int i = 1; i <= n << 1; i++) block[i] = i / len + (i % len > 0);sort(Q + 1, Q + 1 + m);int curl = 1, curr = 0;memset(vis, 0, sizeof(vis));for (int i = 1,l,r; i <= m; i++) {l = Q[i].l; r = Q[i].r;while (curl < l) chan(curl++);while (curl > l) chan(--curl);while (curr < r) chan(++curr);while (curr > r) chan(curr--);ans[Q[i].id] = res;if (Q[i].lca != Q[i].u && !cnt[idx[Q[i].lca]]) ans[Q[i].id]++;}for (int i = 1; i <= m; i++) {write(ans[i]); putchar('\n');}
}

回滚莫队等我写了板子题再写。。。

查看全文

http://www.mrgr.cn/news/40193.html