题解：P8123 [BalticOI 2021] Inside information (Day1)

Bychance · 2026-08-08 16:02:46 · 题解

感觉这题巨大困难啊，但是做了确实对点分治理解更深了。

拜谢 是青白呀 推题以及提供优秀的点分治写法。

题意稍微有点绕，简单来说，S 操作的意思就是 a 和 b 同时获得对方当前拥有的所有数据块，Q 操作就是查询第 a 个服务器是否拥有第 d 块数据，C 操作就是查询有多少个服务器拥有一个数据块。

首先多组询问肯定先考虑离线。

考虑刻画这个事情，对于每一个 S 操作，我们在 a，b 间连一条边，边权为这次操作的时间戳，而对于 Q 操作，我们就是查询 d \rightarrow a 的路径上是否满足边权单调递增（后文记为性质一）且全部小于这次查询的时间戳（后文记为性质二），最后，对于 C 操作，即查找对于一个点，有多少个点满足上面 Q 操作中所说的那样的路径。

这里可以考虑点分治。

• 考虑性质一的处理方式，对于一条经过 x 的路径 u \rightarrow v，类似于分段函数的单调性问题，我们需要满足 u \rightarrow x 单增（也就是 x \rightarrow u 单减），x\rightarrow v 也单增，并且交界处也单增。对于交界处也单增的刻画，即你通过对每个点出边集合排序，使得新加入的每一个点能统计到的贡献全都是合法的。

• 考虑性质二的处理方式，我们发现由于路径的单调性，我们对于一组询问边权最大的那条边一定是在询问中的一个点（也就是所谓的关键点）上的，所以我们处理的时候将答案计入一个树状数组，询问的时候统计前缀和即可。

思路不难，但代码有点难写。

::::info[小清新代码~]

const int N = 1.2e5 + 7;
int n, k;
int sz[N], vis[N];
int lst[N];
int ans[N];
int tr[N << 1];
vector<pii> E[N];

struct query {
    char opt;
    int x, id, qid;
};
vector<query> q[N];

inline void add(int x, int val) {
    for (int i = x; i <= (n - 1 + k); i += i & -i){
        tr[i] += val;
    }
}
inline int ask(int x) {
    int ret = 0;
    for (int i = x; i; i -= i & -i) {
        ret += tr[i];
    }
    return ret;
}

inline void siz(int x, int fa) {//重置树的大小
    sz[x] = 1;
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (to == fa || vis[to]) continue;
        siz(to, x);
        sz[x] += sz[to];
    }
} 
inline int fd(int x, int fa, int rt) {//找重心
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (to == fa || vis[to]) continue;
        if (sz[to] * 2 > sz[rt]) return fd(to, x, rt);
    }
    return x;
}
inline void dec(int x, int fa, int pre) {//搜索递减路径并仅统计越过重心的贡献（不统计这条链上的贡献）
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (to == fa || vis[to] || k > pre) continue;
        dec(to, x, k);
    }
    for (auto it : q[x]) {
        char opt = it.opt;
        if (opt == 'Q') {
            if (lst[it.x] && lst[it.x] < it.id) ans[it.qid] = -1;
        } else {
            ans[it.qid] += ask(it.id);
        }
    }
    //这里不能加入对答案的贡献，不然可能会自己统计到自己
}
inline void inc(int x, int fa, int pre) {//加入这条链上的贡献
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (to == fa || vis[to] || k < pre) continue;
        inc(to, x, k);
    }
    lst[x] = pre, add(pre, 1);
}
inline void del(int x, int fa, int pre) {//撤销这个越过此重心的所有贡献
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (to == fa || vis[to] || k < pre) continue;
        del(to, x, k);
    }
    lst[x] = 0, add(pre, -1);
}
inline void calc(int x) {//计算越过重心的贡献
    for (auto it : E[x]) {
        int to = it.fi, k = it.se;
        if (vis[to]) continue;
        lst[x] = k, add(k, 1);
        dec(to, x, k);
        lst[x] = 0, add(k, -1);
        inc(to, x, k);
    }
    for (auto it : q[x]) {
        char opt = it.opt;
        if (opt == 'Q') {
            if (lst[it.x] && lst[it.x] < it.id || it.x == x) ans[it.qid] = -1;
        } else {
            ans[it.qid] += ask(it.id) + 1;
        }
    }
    for (auto it : E[x]) if (!vis[it.fi])
        del(it.fi, x, it.se);
}
inline void dfs(int x, int fa) {//点分治
    siz(x, 0);
    int pos = fd(x, 0, x);
    calc(pos), vis[pos] = 1;
    for (auto it : E[pos]) {
        int to = it.fi, k = it.se;
        if (vis[to]) continue;
        dfs(to, pos);
    }
}

signed main() {
    std::ios::sync_with_stdio(false);   
    std::cin.tie(0);
    std::cout.tie(0);

    cin >> n >> k;
    int qid = 0;
    rep(i, 1, n - 1 + k) {
        char opt;
        cin >> opt;
        if (opt == 'S') {
            int x, y;
            cin >> x >> y;
            E[x].eb(mkp(y, i));
            E[y].eb(mkp(x, i));
        } else if (opt == 'Q') {
            int x, y;
            cin >> x >> y;
            q[y].pb({opt, x, i, ++qid});
            ans[qid] = -2;
        } else {
            int x;
            cin >> x;
            q[x].pb({opt, x, i, ++qid});
        }
    }
    rep(i, 1, n) sort(E[i].begin(), E[i].end(), [&](pii A, pii B) { return A.se > B.se; });
    dfs(1, 0);
    rep(i, 1, qid) {
        if (ans[i] < 0) cout << (ans[i] == -1 ? "yes" : "no") << '\n';
        else cout << ans[i] << '\n';
    }

    return 0;
}

::::