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

· · 题解

小清新数据结构题。

前两个操作很简单，合并集合与查询元素，直接用线段树合并乱做都行，难点在第三个。

你发现第二个和第三个操作很接近，具体地，我们设边权为时间，那么一个服务器 x 有一个数据块 a，当前仅当从 x 到 a 的边权单调递减，这样才能传递过来，如图：

那么什么样的 x 会满足 a\in S_x 呢？你发现就是 a 到 x 的路径单调递增。既然我们能轻松做到对每个 S_x 有几个元素，那么我们把边权反过来，正好就是每个 a 属于几个集合了！

但你发现一个问题：这样维护的话，我们只能知道最后每个元素在多少集合中出现，但是题目要求是在中间询问怎么办？我们可以维护集合拥有元素的时间，把线段树的作用改成每个时间加入了多少新元素，然后照常线段树合并即可。

贴代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 130000;
int n, m, cnt, rt[N], ans[N << 1];
struct SGT{
    struct node {int ls, rs, siz;}tr[N * 200];
    void insert(int x, int &rt, int l, int r, int pos){
        rt = ++cnt, tr[rt] = tr[x], tr[rt].siz++;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid)insert(tr[x].ls, tr[rt].ls, l, mid, pos);
        else insert(tr[x].rs, tr[rt].rs, mid + 1, r, pos);
    }
    int merge(int x, int y){
        if(!x || !y) return x + y;
        int now = ++cnt;
        tr[now].siz = tr[x].siz + tr[y].siz;
        tr[now].ls = merge(tr[x].ls, tr[y].ls);
        tr[now].rs = merge(tr[x].rs, tr[y].rs);
        return now;
    }
    int find(int x, int l, int r, int pos) {
        if(l == r) return tr[x].siz;
        int mid = (l + r) >> 1;
        if(pos <= mid) return find(tr[x].ls, l, mid, pos);
        return find(tr[x].rs, mid + 1, r, pos);
    }
    int query(int x, int l, int r, int pos) {
        if(l == r) return tr[x].siz;
        int mid = (l + r) >> 1;
        if(pos <= mid) return query(tr[x].ls, l, mid, pos);
        return tr[tr[x].ls].siz + query(tr[x].rs, mid + 1, r, pos);
    }
}sgt;
char c;
struct ques {
    char c;
    int a, b;
} q[N << 1];
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)sgt.insert(rt[i], rt[i], 1, n, i);
    int num = n + m - 1;
    for(int i = 1; i <= num; i++) {
        int a, b = 0;cin >> c >> a;
        if(c == 'S') cin >> b, rt[a] = rt[b] = sgt.merge(rt[a], rt[b]);
        else if(c == 'Q') cin >> b, ans[i] = sgt.find(rt[a], 1, n, b);
        q[i] = {c, a, b};
    }
    for(int i = 0; i <= cnt; i++) sgt.tr[i].ls = sgt.tr[i].rs = sgt.tr[i].siz = 0;
    cnt = 0;
    for(int i = 1; i <= n; i++)rt[i] = 0;
    for(int i = num; i >= 1; i--) 
        if(q[i].c == 'S'){
            int a = q[i].a, b = q[i].b;
            rt[a] = sgt.merge(rt[a], rt[b]), sgt.insert(rt[a], rt[a], 1, num, i), rt[b] = rt[a];
        }

    for(int i = 1; i <= num; i++){
        if(q[i].c == 'Q') cout << (ans[i] ? "yes" : "no") << '\n';
        else if(q[i].c == 'C') cout << sgt.query(rt[q[i].a], 1, num, i) + 1 << '\n';
    }
    return 0;
}