P11943 [KTSC 2025] 粒子对撞 / particles 题解

· · 题解

学完 FHQ 三天后这题出现在模拟赛里。

生成失败就是删点，答案是每个连通块内粒子的个数除以二下取整的和。

设 \text{dfn}_u, \text{low}_u 表示访问和回溯时的 dfn 序。

维护每个连通块内的粒子，删点操作就是把粒子分到新产生的连通块内，先减掉原来的贡献，加上新连通块的贡献即可。使用上述 dfn 序 + FHQ-Treap 容易完成该操作。具体而言，设删除点 u，先把 \text{dfn}_u \leqslant x \leqslant \text{low}_u 的 x 分裂出来，然后用同样方法分裂给 u 的子树，剩余部分分给原来的连通块根。

维护每个点属于哪个连通块用线段树容易完成，插入也就容易了。时间复杂度 O(n \log n)。

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

using namespace std;

namespace particles {

int n;
vector<int> vec[200005];

int f[200005];
int dfn[200005], dfn_clock;
int nfd[200005];
int low[200005];
static inline void dfs(int u, int fa) {
    f[u] = fa;
    nfd[dfn[u] = ++dfn_clock] = u;
    for (auto v : vec[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
    }
    low[u] = dfn_clock;
}

int rt[200005], cnt;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct node {
    int ls, rs, pri, siz, x;
} tr[200005];
static inline int make(int x) {
    tr[++cnt].pri = (int)rnd();
    tr[cnt].siz = 1;
    tr[cnt].x = x;
    return cnt;
}
static inline void pushup(int p) {
    tr[p].siz = tr[tr[p].ls].siz + tr[tr[p].rs].siz + 1;
}
static inline void split(int x, int p, int &u, int &v) {
    if (!p) {
        u = v = 0;
        return;
    }
    if (dfn[tr[p].x] <= x)
        u = p, split(x, tr[p].rs, tr[p].rs, v);
    else
        v = p, split(x, tr[p].ls, u, tr[p].ls);
    pushup(p);
}
static inline int merge(int u, int v) {
    if (!u || !v)
        return u | v;
    if (tr[u].pri < tr[v].pri) {
        tr[u].rs = merge(tr[u].rs, v);
        pushup(u);
        return u;
    } else {
        tr[v].ls = merge(u, tr[v].ls);
        pushup(v);
        return v;
    }
}

int d[800005];
int tag[800005];
static inline void pushtag(int p, int c) {
    d[p] = max(d[p], c);
    tag[p] = max(tag[p], c);
}
static inline void pushdown(int p) {
    pushtag(p << 1, tag[p]);
    pushtag(p << 1 | 1, tag[p]);
    tag[p] = 0;
}
static inline void build(int s, int t, int p) {
    if (s == t) {
        d[p] = 1;
        return;
    }
    int mid = (s + t) >> 1;
    build(s, mid, p << 1);
    build(mid + 1, t, p << 1 | 1);
}
static inline void update(int l, int r, int s, int t, int c, int p) {
    if (l <= s && r >= t) {
        pushtag(p, c);
        return;
    }
    int mid = (s + t) >> 1;
    pushdown(p);
    if (l <= mid)
        update(l, r, s, mid, c, p << 1);
    if (r > mid)
        update(l, r, mid + 1, t, c, p << 1 | 1);
}
static inline int query(int x, int s, int t, int p) {
    if (s == t)
        return d[p];
    int mid = (s + t) >> 1;
    pushdown(p);
    if (x <= mid)
        return query(x, s, mid, p << 1);
    return query(x, mid + 1, t, p << 1 | 1);
}

int ans;

static inline void initialize(int _n, const vector<int> &_u, const vector<int> &_v) {
    n = _n;
    for (int i = 0; i < n - 1; ++i) {
        int u = _u[i] + 1, v = _v[i] + 1;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1, 0);
    build(1, n, 1);
}
static inline void enable(int u) {
    int r = nfd[query(dfn[u], 1, n, 1)];
    ans -= tr[rt[r]].siz >> 1;
    int x;
    split(dfn[u], rt[r], rt[r], x);
    rt[r] = merge(rt[r], merge(make(u), x));
    ans += tr[rt[r]].siz >> 1;
}
static inline void disable(int u) {
    int r = nfd[query(dfn[u], 1, n, 1)];
    ans -= tr[rt[r]].siz >> 1;
    int x, y, z;
    split(dfn[u], rt[r], rt[r], x);
    split(low[u], x, y, z);
    for (auto v : vec[u]) {
        if (v == f[u])
            continue;
        update(dfn[v], low[v], 1, n, dfn[v], 1);
        split(low[v], y, rt[v], y);
        ans += tr[rt[v]].siz >> 1;
    }
    rt[r] = merge(rt[r], z);
    ans += tr[rt[r]].siz >> 1;
}

} // namespace particles

void initialize(int N, vector<int> A, vector<int> B) {
    particles::initialize(N, A, B);
}
int generate(int v, bool result) {
    ++v;
    if (result)
        particles::enable(v);
    else
        particles::disable(v);
    return particles::ans;
}