手把手教你如何卡常

_jxy · 2025-02-20 08:28:47 · 题解

这篇题解将手把手教会你如何卡常。

首先考虑树剖。因为每个子节点只有一个父节点，所以可以拿每个子节点存连接它和它的父亲的那条边的边权。每次只要修改 u 到 v 的点权就好了。这样可以获得 75 分的高分。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct node {
    int l, r, col;
} tri[N * 4];
struct edge {
    int u, v;
} e[N];
int n, m, dep[N], fa[N], top[N], pos[N], sz[N], cnt, son[N];
vector<int> g[N];
void build(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == f) continue;
        build(v, u);
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
        sz[u] += sz[v];
    }
}
void dfs(int u, int h) {
    top[u] = h;
    pos[u] = ++cnt;
    if (son[u] != 0) dfs(son[u], h);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) {
            continue;
        }
        dfs(v, v);
    }
}
void build_tri(int p, int l, int r) {
    tri[p].l = l;
    tri[p].r = r;
    tri[p].col = -1;
    if (l == r) {
        tri[p].col = 0;
        return;
    }
    int mid = l + r >> 1;
    build_tri(p << 1, l, mid);
    build_tri(p << 1 | 1, mid + 1, r);
}
void pushdown(int p) {
    if (tri[p].l == tri[p].r || tri[p].col == -1) {
        return;
    }
    tri[p << 1].col = tri[p << 1 | 1].col = tri[p].col;
    tri[p].col = -1;
}
void update(int p, int l, int r, int col) {
    if (tri[p].l >= l && tri[p].r <= r) {
        tri[p].col = col;
        return;
    }
    pushdown(p);
    int mid = tri[p].l + tri[p].r >> 1;
    if (l <= mid) {
        update(p << 1, l, r, col);
    }
    if (r > mid) {
        update(p << 1 | 1, l, r, col);
    }
}
int query(int p, int x) {
    if (tri[p].l == tri[p].r) return tri[p].col;
    pushdown(p);
    int mid = tri[p].l + tri[p].r >> 1;
    if (x <= mid) {
        return query(p << 1, x);
    } else {
        return query(p << 1 | 1, x);
    }
}
void update_path(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        update(1, pos[top[x]], pos[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    update(1, pos[x] + 1, pos[y], k);
}
int query_path(int x, int y) {
    if (fa[x] == y) {
        return query(1, pos[x]);
    } else {
        return query(1, pos[y]);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
        e[i] = {u, v};
    }
    build(1, 0);
    dfs(1, 1);
    build_tri(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int x, y, col = i;
        scanf("%d%d", &x, &y);
        update_path(x, y, col);
    }
    for (int i = 1; i < n; i++) {
        printf("%d ", query_path(e[i].u, e[i].v));
    }
    return 0;
}

这个时候你发现超时的点数不多，明显卡卡常就能过去。

于是考虑卡常。

先将线段树的修改操作离线，存在一个 vector 里面，最后一起修改。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct node {
    int l, r, col;
} tri[N * 4];
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
    int x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57) {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57)
        x = x * 10 + ch - 48, ch = nc();
    return x * f;
}
struct edge {
    int u, v;
} e[N];
int n, m, dep[N], fa[N], top[N], pos[N], sz[N], cnt, son[N];
vector<int> g[N];
inline void build(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == f) {
            continue;
        }
        build(v, u);
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
        sz[u] += sz[v];
    }
}
inline void func(int u, int tot) {
    top[u] = tot;
    pos[u] = ++cnt;
    if (son[u] != 0) {
        func(son[u], tot);
    }
    for (int v : g[u]) {
        if (v == fa[u] or v == son[u]) {
            continue;
        }
        func(v, v);
    }
}
inline void build_tri(int p, int l, int r) {
    tri[p].l = l;
    tri[p].r = r;
    tri[p].col = -1;
    if (l == r) {
        tri[p].col = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build_tri(p << 1, l, mid);
    build_tri(p << 1 | 1, mid + 1, r);
}
inline void pushdown(int p) {
    if (tri[p].l == tri[p].r or tri[p].col == -1) {
        return;
    }
    tri[p << 1].col = tri[p << 1 | 1].col = tri[p].col;
    tri[p].col = -1;
}
inline void update(int p, int l, int r, int col) {
    if (tri[p].l >= l and tri[p].r <= r) {
        tri[p].col = col;
        return;
    }
    pushdown(p);
    int mid = (tri[p].l + tri[p].r) >> 1;
    if (l <= mid) {
        update(p << 1, l, r, col);
    }
    if (r > mid) {
        update(p << 1 | 1, l, r, col);
    }
}
inline int query(int p, int x) {
    if (tri[p].l == tri[p].r) {
        return tri[p].col;
    }
    pushdown(p);
    int mid = (tri[p].l + tri[p].r) >> 1;
    if (x <= mid) {
        return query(p << 1, x);
    } else {
        return query(p << 1 | 1, x);
    }
}
struct Node {
    int x, y, k;
};
vector<Node> vec;
inline void update_path(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        // update(1, pos[top[x]], pos[x], k);
        vec.push_back({pos[top[x]], pos[x], k});
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    vec.push_back({pos[x] + 1, pos[y], k});
    // update(1, pos[x] + 1, pos[y], k);
}
inline int query_path(int x, int y) {
    if (fa[x] == y) {
        return query(1, pos[x]);
    } else {
        return query(1, pos[y]);
    }
}
int main() {
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
        e[i] = {u, v};
    }
    build(1, 0);
    func(1, 1);
    build_tri(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), col = i;
        update_path(x, y, col);
    }
    for (auto [x, y, k] : vec) {
        update(1, x, y, k);
    }
    for (int i = 1; i < n; i++) {
        printf("%d ", query_path(e[i].u, e[i].v));
    }
    return 0;
}

这份代码快的起飞，只超时 4 个点。

这时，你发现因为查询都在修改之后，而且每个位置在查询时都会被访问多次，所以给它记忆化一下就过了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct node {
    int l, r, col;
} tr[N * 4];
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
    int x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57) {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = nc();
    return x * f;
}
void write(const int &x) {
    int num = x;
    string str;
    do {
        str.push_back(num % 10 + '0');
        num /= 10;
    } while (num);
    for (int i = str.size() - 1; i >= 0; i--) putchar(str[i]);
    return;
}
struct edge {
    int u, v;
} e[N];
int n, m, dep[N], fa[N], top[N], pos[N], sz[N], cnt, son[N];
vector<int> g[N];
inline void build(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == f) continue;
        build(v, u);
        if (sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
    }
}
inline void dfs(int u, int h) {
    top[u] = h;
    pos[u] = ++cnt;
    if (son[u]) dfs(son[u], h);
    for (auto v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs(v, v);
    }
}
inline void build_tri(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].col = -1;
    if (l == r) {
        tr[u].col = 0;
        return;
    }
    int mid = l + r >> 1;
    build_tri(u << 1, l, mid);
    build_tri(u << 1 | 1, mid + 1, r);
}
inline void pushdown(int u) {
    if (tr[u].l == tr[u].r || tr[u].col == -1) return;
    tr[u << 1].col = tr[u << 1 | 1].col = tr[u].col;
    tr[u].col = -1;
}
inline void update(int u, int l, int r, int col) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].col = col;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, col);
    if (r > mid) update(u << 1 | 1, l, r, col);
}
int f[N << 2];
inline int query(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].col;
    pushdown(u);
    if (f[x]) return f[x];
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) {
        return f[x] = query(u << 1, x);
    } else {
        return f[x] = query(u << 1 | 1, x);
    }
}
struct Node {
    int x, y, k;
};
vector<Node> vec;
inline void update_path(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        vec.push_back({pos[top[x]], pos[x], k});
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    vec.push_back({pos[x] + 1, pos[y], k});
}
inline int query_path(int x, int y) {
    if (fa[x] == y) {
        return query(1, pos[x]);
    } else {
        return query(1, pos[y]);
    }
}
int main() {
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
        e[i] = {u, v};
    }
    build(1, 0);
    dfs(1, 1);
    build_tri(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        update_path(x, y, i);
    }
    for (auto [x, y, k] : vec) update(1, x, y, k);
    for (int i = 1; i < n; i++) {
        write(query_path(e[i].u, e[i].v));
        putchar(' ');
    }
    return 0;
}

AC记录