首页 > 其他分享 >莫队从入门到人门

莫队从入门到人门

时间：2024-12-25 21:08:56浏览次数：9  
标签：cnt 人门 入门 int res add ++ depth 莫队

普通莫队

详介（P2709 小B的询问）

普通莫队处理问题的前提是问题可以离线，多次区间查询，\(O(n\sqrt m)\) 能过。

我们以 P2709 小B的询问 为例，假设当前区间为 \([l,r]\)，答案为 \(ans\)，那么 \(r\) 右移一位时，新加入一个数 \(x\)，我们只要把 \(ans\) 加上 \(x\) 的贡献即可。贡献只需要维护一下当前区间内 \(x\) 的出现次数 \(cnt[x]\) 即可。

所以我们可以初始 \(l = 1, r = 0\)，每次向一个询问的区间移动 \(l\) 和 \(r\)，然后维护当前区间的答案。

我们发现，如果两个查询区间的差距很大，我们每次就要跑很远才能到答案，所以我们要将所有的询问离线下来，进行分块和排序。

具体地，我们将所有的询问进行分块，将所有的询问按照左端点所在块为第一关键字，右端点升序进行排序，这样排完序后我们发现在一个块中 \(r\) 的移动为 \(O(n)\)，设当前块长为 \(B\)，那么总共就是 \(O(\frac{n^2}{B})\)，而左端点在每两个询问之间移动次数不超过 \(O(B)\)，所以总共为\(O(mB)\)，两者相加就是 \(O(mB + \frac{n^2}{B})\)。发现取 \(B\) 为 \(\frac{n}{\sqrt m}\) 时复杂度最优为 \(O(n\sqrt m)\)。

这是 \(P2709\) 的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50010;
int n, m, k, w[N], B, cnt[N], ans[N];
LL res;

struct node {
    int l, r, id;
    bool operator < (const node &t) const {
        if (l / B == t.l / B) return r < t.r;
        else return l / B < t.l / B;
    }
} q[N];

void add(int x) {
    res -= cnt[x] * cnt[x];
    cnt[x] ++;
    res += cnt[x] * cnt[x];
}

void del(int x) {
    res -= cnt[x] * cnt[x];
    cnt[x] --;
    res += cnt[x] * cnt[x];
}

int main() {
    scanf("%d%d%d", &n, &m, &k); B = sqrt(n);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i ++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; }

    sort(q + 1, q + 1 + m);

    int l = 1, r = 0;
    for (int i = 1; i <= m; i ++) {
        while (l > q[i].l) add(w[-- l]);
        while (r < q[i].r) add(w[++ r]);
        while (l < q[i].l) del(w[l ++]);
        while (r > q[i].r) del(w[r --]);
        ans[q[i].id] = res;
    }

    for (int i = 1; i <= m; i ++) printf("%d\n", ans[i]);
    return 0;
}

P1494 小 Z 的袜子

这同样是一道莫队题，我们发现答案应该是：

\[\frac{\sum{col}\ cnt_{col} \times (cnt_{col} - 1)}{(R - L + 1) \times (R-L)} \]

其中 \(col\) 是 \([L,R]\) 中出现的所有颜色，\(cnt_{col}\) 是该颜色出现的次数，我们修改一下莫队的 \(add\) 和 \(del\)，维护分子即可。

记得约分和特判。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50010;
int n, m, k, w[N], B, cnt[N], ans[N], ans2[N];
LL res;

struct node {
    int l, r, id;
    bool operator < (const node &t) const {
        if (l / B == t.l / B) return r < t.r;
        else return l / B < t.l / B;
    }
} q[N];

void add(int x) {
    res -= cnt[x] * (cnt[x] - 1) / 2;
    cnt[x] ++;
    res += cnt[x] * (cnt[x] - 1) / 2;
}

void del(int x) {
    res -= cnt[x] * (cnt[x] - 1) / 2;
    cnt[x] --;
    res += cnt[x] * (cnt[x] - 1) / 2;
}

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

int main() {
    scanf("%d%d", &n, &m); B = sqrt(n);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i ++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; }

    sort(q + 1, q + 1 + m);

    int l = 1, r = 0;
    for (int i = 1; i <= m; i ++) {
        while (l > q[i].l) add(w[-- l]);
        while (r < q[i].r) add(w[++ r]);
        while (l < q[i].l) del(w[l ++]);
        while (r > q[i].r) del(w[r --]);
        ans[q[i].id] = res; ans2[q[i].id] = (LL)(r - l + 1) * (r - l) / 2;
    }

    for (int i = 1; i <= m; i ++) {
        if (ans[i] == 0) ans2[i] = 1;
        LL g = gcd(ans[i], ans2[i]);
        printf("%lld/%lld\n", ans[i] / g, ans2[i] / g);
    }
    return 0;
}

可能还有例题，后面再做。

带修莫队

详介

带修莫队可以理解为一种广义高维莫队，顾名思义，可以支持修改。做法也十分简单，我们只需要给莫队增加一维时间即可。时间指的是在这个查询操作前一共有多少个修改操作。由于加了一维时间，所以我们可以按照第一维左端点所在块，第二维右端点所在块，第三维时间，分别从小到大排序。

struct query {
    int l, r, id, t;
    bool operator < (const query &T) const {
        if (l / B != T.l / B) return l / B < T.l / B;
        else if (r / B != T.r / B) return r / B < T.r / B;
        else return t < T.t;
    }
} q[N];

同时我们还需要存一下所有的修改操作。

struct operation {
    int p, x;
} op[N];

莫队如何维护时间维呢？我们发现如果当前的修改的 \(p\) 属于当前莫队区间 \([l,r]\)，那么就对第 \(p\) 个位置原本的数 \(y\) 做 \(del(y)\)，然后再对于修改的 \(x\) 做 \(add(x)\)，最后由于每一个修改操作的使用和清除一定是成对出现的，所以我们直接将 \(x\) 和 \(y\) 进行交换即可。

void upd(int last, int l, int r) { // last 是当前操作编号
    if (op[last].p >= l && op[last].p <= r) {
        add(op[last].x);
        del(a[op[last].p]);
    }
    swap(op[last].x, a[op[last].p]);
}

我们再考虑块长应该取多少，我们直接考虑 \(k\) 维莫队，其中前 \(k - 1\) 维按所在块升序，第 \(k\) 维升序，那么一共会出现 \((\frac{n}{B})^{k-1}\) 种块的情况，每种情况下右端点最多移动 \(O(n)\)，每切换一次询问左端点最多移动 \(O((k-1)B)\)，所以总的时间复杂度就应该是 \(O((\frac{n}{B})^{k-1} \times n + (k-1)Bm)\)，根据基本不等式当 \(B = \sqrt[k]{\frac{n^k}{(k-1)m}}\) 时取到最优，如果将 \((k-1)\) 视为常数，并且 \(n、m\) 同阶，那么 \(B\) 就可以取到 \(n^{\frac{k-1}{k}}\)。

回到带修莫队，就相当于一个三维的莫队，那么 \(B\) 就取 \(n^{\frac{2}{3}}\)，带回计算可得到时间就是 \(O(n^{\frac{5}{3}} + 2 \times n^{\frac{1}{3}}m)\)，可以看做 \(O(n^{\frac{5}{3}})\)。

例题 P1903 数颜色

贴一份带修莫队的代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 150010, M = 1000010;
int n, m, a[N], B;
int cnt[M], res, qcnt, opcnt;
int ans[N];

struct query {
    int l, r, id, t;
    bool operator < (const query &T) const {
        if (l / B != T.l / B) return l / B < T.l / B;
        else if (r / B != T.r / B) return r / B < T.r / B;
        else return t < T.t;
    }
} q[N];

struct operation {
    int p, x;
} op[N];

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

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

void upd(int last, int l, int r) {
    if (op[last].p >= l && op[last].p <= r) {
        add(op[last].x);
        del(a[op[last].p]);
    }
    swap(op[last].x, a[op[last].p]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    B = pow(n, 2.0 / 3.0);

    for (int i = 1; i <= m; i ++) {
        char t[2]; int l, r;
        scanf("%s%d%d", t, &l, &r);
        if (*t == 'Q') q[++ qcnt] = {l, r, qcnt, opcnt};
        else op[++ opcnt] = {l, r};
    }

    sort(q + 1, q + 1 + qcnt);

    int l = 1, r = 0, last = 0;
    for (int i = 1; i <= qcnt; i ++) {
        while (l > q[i].l) add(a[-- l]);
        while (r < q[i].r) add(a[++ r]);
        while (l < q[i].l) del(a[l ++]);
        while (r > q[i].r) del(a[r --]);
        while (last < q[i].t) upd(++ last, l, r);
        while (last > q[i].t) upd(last --, l, r);
        ans[q[i].id] = res;
    }

    for (int i = 1; i <= qcnt; i ++) printf("%d\n", ans[i]);
    return 0;
}

树上莫队

详介 (SP10707 COT2 - Count on a tree II)

顾名思义，是在“树上”的莫队。我们来看一个例子（就是本段标题的题目），要求树上路径上的不同颜色数。

我们发现在树上进行莫队十分的不方便，我们考虑将其转化成一维的序列。我们可以使用欧拉序。

对于这幅图，它的欧拉序（以 \(1\) 为更）便是 \([1,3,5,5,6,6,7,7,3,2,2,4,8,8,4,1]\)。我们考虑一个点 \(u\) 到 \(v\) 的路径在欧拉序中的表示，我们记 \(st[x]\) 和 \(ed[x]\) 分别表示一个点的第一次和最后一次出现的位置，那么我们可以分类讨论（假定 \(st[u] < st[v]\)）：

  1. \(u\) 是 \(v\) 的祖宗，如 \(1 -> 6\)，我们可以截取欧拉序中的 \([1,3,5,5,6]\)，即 \(st[1] \sim st[6]\) 之间的所有。我们发现 \(5\) 出现了两次，相当于进去了有出来，可以删掉，剩下的 \([1,3,6]\) 便是我们的路径。
  2. \(u\) 不是 \(v\) 的祖宗，如 \(3 -> 8\)，那么我们截取 \(ed[3] \sim st[8]\) 之间的所有，再删去出现两次的 \(2\)，剩下 \([3,4,8]\) 我们发现路径中还少了 \(3\) 和 \(8\) 的 \(lca\)，加上即可。

综上，我们可以将 \(u -> v\) 的路径用欧拉序巧妙的表示。这样子树上的询问就变成区间，可以使用莫队。由于我们使用的是普通莫队，所以块长为 \(\frac{n}{\sqrt m}\)。同时，为了维护一个点的出现次数，我们可以使用异或，\(0\) 表示该点第一次出现，可加入，\(1\) 表示第二次，要删除。

注意到颜色 \(\leq 2e9\)，需要离散化。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 100010;
int n, m, w[N];
int h[N], e[N], ne[N], idx;
int fa[N][20], depth[N], in[N];
int st[N], ed[N], q[N], len;
int vis[N], cnt[N], res, ans[M];
int c[N];
vector<int> v;

int find(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

void add_edge(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// lca 的预处理
void bfs(int root) {
    queue<int> q; q.push(root);
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q.push(j);
                for (int k = 1; k < 20; k ++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

// 预处理欧拉序
void dfs(int u, int fa) {
    q[++ len] = u, st[u] = len;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
    }
    q[++ len] = u, ed[u] = len;
}

// 倍增求 lca
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 19; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }  
    return fa[a][0];
}

int B;
struct query {
    int l, r, id, lca;
    bool operator < (const query &t) const {
        return l / B < t.l / B || l / B == t.l / B && r > t.r;
    }
} que[N];

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

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

void upd(int x) {
    if (!vis[x]) add(c[x]);
    else del(c[x]);
    vis[x] ^= 1;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    B = n / sqrt(m);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &w[i]);
        v.push_back(w[i]);
    }
    for (int i = 1; i < n; i ++) {
        int a, b; scanf("%d%d", &a, &b);
        add_edge(a, b); add_edge(b, a);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i ++) c[i] = find(w[i]);

    bfs(1); dfs(1, -1);

    for (int i = 1; i <= m; i ++) {
        int u, v; scanf("%d%d", &u, &v);
        int s = lca(u, v);
        if (s == u || s == v) {
            if (st[v] < st[u]) swap(u, v);
            que[i] = {st[u], st[v], i};
        } else {
            if (ed[v] < st[u]) swap(u, v);
            que[i] = {ed[u], st[v], i, s};
        }
    }

    sort(que + 1, que + 1 + m);

    int l = 1, r = 0;
    for (int i = 1; i <= m; i ++) {
        while (l > que[i].l) upd(q[-- l]);
        while (r < que[i].r) upd(q[++ r]);
        while (l < que[i].l) upd(q[l ++]);
        while (r > que[i].r) upd(q[r --]);
        if (que[i].lca) upd(que[i].lca);
        ans[que[i].id] = res;
        if (que[i].lca) upd(que[i].lca);
    }
    
    for (int i = 1; i <= m; i ++) printf("%d\n", ans[i]);

    return 0;
}

P4074 糖果公园

注意到题目求的其实就是 \(u->v\) 路径上的 \(\sum_{col\in c_{u->v}}\ v_{col}\times \sum{w_{col}}\)，并且需要支持修改，我们使用树上莫队和带修莫队的融合版即可。

代码有点复杂。注意 \(modify\) 中的 \(x\) 是 \(p\) 位置在进行本次修改前应该是什么值，而 \(t\) 存的是本次修改后的值。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m, Q;
int v[N], w[N], c[N], last[N];
int h[N], e[N], ne[N], idx;
int fa[N][22], depth[N];
int q[N], st[N], ed[N], len;
LL cnt[N], dis[N], ans[N], cntw[N];
LL res;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}   

void bfs(int root) {
    queue<int> q; q.push(root);
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q.push(j);
                for (int k = 1; k <= 20; k ++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

void dfs(int u, int fa) {
    q[++ len] = u, st[u] = len;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
    }
    q[++ len] = u, ed[u] = len;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 20; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }  
    return fa[a][0];
}

int B, qcnt, rcnt;
struct Query {
	int l, r, id, t, lca;
	bool operator < (const Query &T) const {
		if (l / B != T.l / B) return l / B > T.l / B;
		else if (r / B != T.r / B) return r / B > T.r / B;
		else return t > T.t;
	}
} query[N];

struct Modify {
	int p, x, t;
} modify[N];

// 写法和上一题不一样，感觉 OIWiki 上的更简洁一点
void add(int x) {
    if (dis[x]) res -= (LL)v[c[x]] * w[cnt[c[x]]--];
    else res += (LL)v[c[x]] * w[++ cnt[c[x]]];
    dis[x] ^= 1;
}

void upd(int p, int x) {
    if (dis[p]) {
        add(p); c[p] = x; add(p);
    } else c[p] = x;
} 

int main() {
	scanf("%d%d%d", &n, &m, &Q);
	memset(h, -1, sizeof h);
	for (int i = 1; i <= m; i ++) scanf("%d", &v[i]);
	for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
	for (int i = 1; i < n; i ++) {
		int a, b; scanf("%d%d", &a, &b);
		add(a, b); add(b, a);
	}
	for (int i = 1; i <= n; i ++) { scanf("%d", &c[i]); last[i] = c[i]; }
	
	bfs(1); 
	dfs(1, -1);
	
	B = pow(len, 2.0 / 3.0);
	while (Q --) {
		int op, x, y; scanf("%d%d%d", &op, &x, &y);
		if (op == 0) {
            // last[x] 表示位置 x 修改前的值
			modify[++ rcnt] = {x, last[x]};
            last[x] = modify[rcnt].t = y;
		} else {
			int s = lca(x, y);
			if (s == x || s == y) {
				if (st[y] < st[x]) swap(x, y);
				query[++ qcnt] = {st[x], st[y], qcnt, rcnt, 0};
			} else {
				if (st[y] < st[x]) swap(x, y);
				query[++ qcnt] = {ed[x], st[y], qcnt, rcnt, s};
			}
		}
	}
	
	sort(query + 1, query + 1 + qcnt);
	int l = 1, r = 0, last = 0;
	for (int i = 1; i <= qcnt; i ++) {
		while (l > query[i].l) add(q[-- l]);    
		while (r < query[i].r) add(q[++ r]);
		while (l < query[i].l) add(q[l ++]);
		while (r > query[i].r) add(q[r --]);    
        // 这里注意，拓展时用的是修改后的值，恢复时用的是修改前的值
		while (last < query[i].t) last ++, upd(modify[last].p, modify[last].t);
		while (last > query[i].t) upd(modify[last].p, modify[last].x), last --;    
		if (query[i].lca) add(query[i].lca);
		ans[query[i].id] = res;
		if (query[i].lca) add(query[i].lca);
	}
	
	for (int i = 1; i <= qcnt; i ++) printf("%lld\n", ans[i]);
	return 0;
}

回滚莫队

在写

标签：cnt,人门,入门,int,res,add,++,depth,莫队
From： https://www.cnblogs.com/biyimouse/p/18631414

相关文章

  • GCC安装入门教程（非常详细）从零基础入门到精通，看完这一篇就够了
    1.下载GCC安装包，下载地址如下，选择需要的安装版本：https://mirrors.tuna.tsinghua.edu.cn/gnu/gcc/2.解压配置进入解压目录执行：./configure可能会遇到下面的问题：configure:error:BuildingGCCrequiresGMP4.2+,MPFR2.4.0+andMPC0.8.0+.Trythe--with-gmp,--w......
  • Notepad ++ 安装与配置教程（非常详细）从零基础入门到精通，看完这一篇就够了
    Notepad++获取与安装——————————Notepad++是什么在运行中输入notepad会弹出来记事本：所以Notepad++就是增强的记事本！这个跟C与C++的名字是一样滴！Notepad++是开源软件GPL许可证可以免费使用自带中文支持很多计算机编程......
  • Jenkins入门使用
    Jenkins入门使用1先安装jdk才能运行jenkinsyuminstall-yjava-1.8.0-openjdk.x86_642安装jenkins，运行，进行端口绑定，启动jenkinsdockersearchjenkinsdockerpulljenkins/jenkinsdockerrun-d-uroot-p8080:8080-p50000:50000-v/var/jenkins_home:/var/jenkin......
  • 完全小白的大模型入门科普
    引言：网上关于大模型的文章也很多，但是都不太容易看懂。小枣君今天试着写一篇，争取做到通俗易懂。废话不多说，我们直入主题。█什么是大模型？大模型，英文名叫LargeModel，大型模型。早期的时候，也叫FoundationModel，基础模型。大模型是一个简称。完整的叫法，应该是“人工智能预训练......
  • 仓颉编程语言首次使用体验——windows下环境配置及入门
    仓颉编程语言是华为研发的一种静态强类型、编译型语言。注意这里的静态，强类型，编译型。同时符合这三个特性的常见语言有：C++RustGoSwiftJava（有区别，java编译为字节码）如果你熟悉上面这些语言，就可以立马了解对仓颉语言有一些感性的认识，这意味仓颉并不是像javascript，python这种语......
  • WEB安全基础入门小知识
    今天给大家科普科普信息安全的一些基础入门小知识: 常见的服务器脚本有哪些？----1:Asp  aspx  [windows]  2:PHP[全平台]3: JSP[全平台]  [JAVA]4: python[全平台]  PS:后端语言是对服务器行为的编程，被称为服务器端脚本和服务器脚本。后端语言......
  • Ginkgo 入门
    在本节中，我们将介绍安装Ginkgo、Gomega和ginkgoCLI。我们启动一个Ginkgo套件，编写我们的第一个规格，并运行它。安装GinkgoGinkgo使用go模块。将Ginkgo添加到项目中，假设有一个go.mod文件设置，只需goinstall即可：：goinstallgithub.com/onsi/ginkgo/v2/ginkgogogetgithub.com/on......
  • Next.js 14 基础入门：从项目搭建到核心概念
    Next.js14带来了许多激动人心的新特性，包括局部渲染、ServerActions增强等。作为一名前端开发者，我最近在项目中升级到了Next.js14，今天就来分享一下从项目搭建到实际应用的完整过程。项目初始化首先，让我们创建一个全新的Next.js14项目：#使用create-next-app创建项目n......
  • 计算机网络入门
    https://studygolang.com/articles/11586#google_vignettehttps://www.oneyearago.me/2019/06/14/learn_gwf/https://www.topgoer.com/网络编程/socket编程/TCP编程.html草率的入门，或许需要从不同的地方获取常识。前置一来就看7层模型给我整蒙了。首先网络是有线的。然后......
  • 零基础入门Spring源码
    文章目录前言Spring相关代码pom.xml配置文件beans.xml实体类测试类一、创建BeanFactoryApplicationContextBeanFactory和ApplicationContext的区别补充如何从容器中获取对象？二、读取xml等，将bean定义信息放入BeanDefinition三、对BeanDefinition中的属性值进行替换补充......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99