牛客练习赛70 D 数树

数树

https://ac.nowcoder.com/acm/contest/7509/D

没看到题目中条件保证是一颗森林,自行加强题目。
这里采用时间线段树+回退并查集来解决。
并查集可以O(1)的插入,很难O(1)的支持删除操作,但是可以回退。
我们使用时间线段树,将所有操作锁定为插入操作,使用回退并查集维护即可。
复杂度O(nlogn)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1
#define MP make_pair

const int N = 2e5 + 100;

int n, tp, tt;
int op[N], uu[N], vv[N], id[N], has[N], ans[N];
pair<int, int> mp[N];
int tim[N];

struct node {
    int op, u, v;
    node() {}
    node(int op, int u, int v) :op(op), u(u), v(v) {}
};

vector<node> V[N * 4], G[N * 4];

void insert(int rl, int rr, node x, int l, int r, int rt) {
    if (rl == l && rr == r) {
        V[rt].push_back(x);
        return;
    }
    int m = (l + r) / 2;
    if (rr <= m) insert(rl, rr, x, l, m, lson);
    else if (m < rl) insert(rl, rr, x, m + 1, r, rson);
    else {
        insert(rl, m, x, l, m, lson);
        insert(m + 1, rr, x, m + 1, r, rson);
    }
}

int fa[N], sz[N], sum;

void change(int op, int id, int x, vector<node> &V) {
    if (op == 1) {
        V.push_back(node(op, id, fa[id]));
        fa[id] = x;
    }
    if (op == 2) {
        V.push_back(node(op, id, sz[id]));
        sz[id] = x;
    }
    if (op == 3) {
        V.push_back(node(op, 0, sum));
        sum = x;
    }
}

void recover(node x) {
    if (x.op == 1) {
        fa[x.u] = x.v;
    }
    if (x.op == 2) {
        sz[x.u] = x.v;
    }
    if (x.op == 3) {
        sum = x.v;
    }
}

int find(int x, vector<node> &V) {
    if (x == fa[x]) return x;
    int f = find(fa[x], V);
    change(1, x, f, V);
    return f;
}

void join(int u, int v, vector<node> &V) {
    u = find(u, V);
    v = find(v, V);
    if (u == v) return;
    if (sz[u] == 1 && sz[v] == 1) change(3, 0, sum + 1, V);
    if (sz[u] > 1 && sz[v] > 1) change(3, 0, sum - 1, V);
    change(1, u, v, V);
    change(2, v, sz[u] + sz[v], V);
}

void query(int l, int r, int rt) {
    for (node x : V[rt]) {
        if (x.op == 1) {
            join(x.u, x.v, G[rt]);
        }
    }
    if (l == r) {
        for (node x : V[rt]) {
            if (x.op == 3) {
                ans[l] = sum;
            }
        }
    }
    else {
        int m = (l + r) / 2;
        query(l, m, lson);
        query(m + 1, r, rson);
    }
    for (int i = G[rt].size() - 1; i >= 0; i--) {
        recover(G[rt][i]);
    }
    G[rt].clear();
    V[rt].clear();
    vector<node> v, g;
    swap(G[rt], g);
    swap(V[rt], v);
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", op + i);
        if (op[i] != 3) {
            scanf("%d%d", uu + i, vv + i);
            has[++tp] = uu[i];
            has[++tp] = vv[i];
        }
    }
    sort(has + 1, has + tp + 1);
    tp = unique(has + 1, has + tp + 1) - has;
    for (int i = 1; i <= n; i++) {
        if (op[i] != 3) {
            uu[i] = lower_bound(has + 1, has + tp, uu[i]) - has;
            vv[i] = lower_bound(has + 1, has + tp, vv[i]) - has;
            if (uu[i] > vv[i]) swap(uu[i], vv[i]);
            mp[++tt] = MP(uu[i], vv[i]);
        }
    }
    sort(mp + 1, mp + tt + 1);
    tt = unique(mp + 1, mp + tt + 1) - mp;
    for (int i = 1; i <= n; i++) {
        if (op[i] == 3) continue;
        int id = lower_bound(mp + 1, mp + tt, MP(uu[i], vv[i])) - mp;
        if (op[i] == 1) {
            if (tim[id] == 0) {
                tim[id] = i;
            }
        }
        else {
            if (tim[id] != 0) {
                insert(tim[id], i, node(1, uu[i], vv[i]), 1, n, 1);
            }
            tim[id] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (op[i] == 3) {
            insert(i, i, node(3, 0, 0), 1, n, 1);
        }
        else if (op[i] == 1) {
            int id = lower_bound(mp + 1, mp + tt, MP(uu[i], vv[i])) - mp;
            if (tim[id] == i) {
                insert(i, n, node(1, uu[i], vv[i]), 1, n, 1);
            }
        }
    }
    for (int i = 1; i <= tp; i++) fa[i] = i, sz[i] = 1;
    query(1, n, 1);
    for (int i = 1; i <= n; i++)
        if (op[i] == 3)
            printf("%d\n", ans[i]);
    return 0;
}
全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务